_LETTERS_


[LISTING ONE]

#include <string.h>

int stcknum;
char *ststr1l[26];
char *ststr2l[26];
char *ststr1r[26];
char *ststr2r[26];

int simil (str1, str2)    /*`Pattern Matching by Gestalt' */
char *str1, *str2;        /*by John W. Ratcliff           */
                          /*Dr. Dobb's Journal #141.      */
{                         /*July 1988                     */
    int len1;
    int len2;
    int ncmp;
    int score;
    char *di;
    char *si;
    char *de;
    char *se;
    char *cl1
    char *cl2;
    char *cr1;
    char *cr2;

    score = 0;
    stcknum = 0;

    len1 = strlen(str1);
    len2 = strlen(str2);
    if (len1 == 0 || len2 == 0)
       return (score);

    pushst (str1, str1+len1-1, str2, str2+len2-1);

    while (stcknum != 0)
    {
        popst (&si, &se, &di, &de);
        cl1 = si;
        cl2 = di;
        cr1 = se;
        cr2 = de;
        if ((ncmp=compare (&si, &se, &di, &de)) !=0)
        {
            score += ncmp*2;
            if (cl1 != si    && cl2 != di   &&
               (cl1 != si-1  || c12 != di-1))
               pushst (cl1, si-1, cl2, di-1);
            if (se    != cr1 && de    != cr2 &&
               (se+1  != cr1 || de+1  != cr2))
               pushst   (se+1, cr1, de+1, cr2);
         }
     }
     return  (100*score/(len1+len2));
}

int compare (si, se, di, de)
char **si;
char **se;
char **di;
char **de;
{
  int maxchars;
  int l;
  int len1;
  char *i;
  char *j;
  char *m;
  char *n;
  char *s2end;
  char *cl1;
  char *cl2;
  char *cr1;
  char *cr2;

  maxchars = 0
  for (i=(*si); i <= *se-maxchars; i++)
  {
      len1 + *se - i;
      for (j=(*di); j <= *de-maxchars; j++)
      {
         s2end = j + len1;
         if (s2end > *de)
             s2end = *de;
         for (m=i,n=j,l=0;  *m==*n && n <=s2end; m++,n++)
             l++;
         if (1 > 0)
         {
            if (l <= maxchars)
            {
                j += l-1;
            }
            else
            {
                cl1 = i;
                cl2 = j;
                maxchars = 1;
                l--;
                j += l;
                cr2 = j;
                cr1 = i+l;
             }
         }
      }
  }
  *si = cl1;
  *se = cr1;
  *di = cl2;
  *de = cr2;
  return (maxchars);
}

pushst (si, se, di, de)
char *si;
char *se;
char *di;
char *de;
{
   ststr1l[stcknum] = si;
   ststr1r[stcknum] = se;
   ststr2l[stcknum] = di;
   ststr2r[stcknum] = de;
   stcknum++;
}

popst (si, se, di, de)
char **si;
char **se;
char **di;
char **de;
{
    stcknum--;
    *si = ststr1l[stcknum];
    *se = ststr1r[stcknum];
    *di = ststr2l[stcknum];
    *de = ststr2r[stcknum];
}




[LISTING TWO] 

int simil (s1, s2)
/* Ratcliff/Obershelp Pattern Matching */
char *1, *2;
{
  short l1, l2;

  l1 = strlen(s1);
  l2 = strlen(s2);

  if (l1 == 1)                 /* check for the easiest case */
    if (l2 == 1)
      if (*s1 == *s2)
        return(100);

  return(200 * GCsubstr(s1, s1 + l1, s2, s2 + l2) / (l1 + l2));
}

int GCsubstr(st1, end1, st2, end2)
/* recursive greatest common sub-string */
char *st1, *end1, *st2, *end2;
{
  register char *a1, *b1, *s1, *a2, *b2, *s2;
  short max, i;

  if (end1 <= st1)              /* s1 empty */
    return (0);
  if (end2 <= st2)              /* s2 empty */
    return (0);
  if (end1 == st1 + 1)          /* s1 has one char, */
    if (end2 == st2 + 1)        /* and s2 has one char. */
      return(0);                /* They cannot be equal. */

  max = 0;
  b1 = end1; b2 = end2;

  for (a1 = st1; a1 < b1; a1++)
    for (a2 = st2; a2 < b2; a2++)
      if (*a1 == *a2)
        {               /* How long is the common sub-string? */
        for (i = 1; a1[i] && (a1[i] == a2[i]); i++)
          ;
        if (i > max)
          {
          max = i; s1 = a1; s2 = a2;
          b1 = end1 - max; b2 = end2 - max;
          }
        }
  if (! max)
    return (0);
  
  max += GCsubstr(s1 + max, end1, s2 + max, end2);        /* RHS */
  max += GCsubstr(st1, s1, st2, s2);                      /* LHS */
  
  return(max);
}