typedef struct pattern_scan_order {

      int loc;

      char c;

   } PAT;

   

   int MinShift[XSIZE];

   

   /* Computation of the MinShift table values. */

   void COMPUTE_MINSHIFT(char *x, int m)

   {

    int i, j;

   

    for (i=0; i < m; i++) {

       for (j=i-1; j >= 0; j--)

           if (x[j] == x[i]) break;

       MinShift[i]=i-j;

    }

   }

   

   /* Construct an ordered pattern from a string. */

   void ORDER_PATTERN(char *x, int m, int (*pcmp)(), PAT *pattern)

   {

    int i;

   

    for (i=0; i <= m; i++) {

       pattern[i].loc=i;

       pattern[i].c=x[i];

    }

    qsort(pattern, m, sizeof(PAT), pcmp);

   }

   

   

   /* Maximal Shift pattern comparison function. */

   int MAXSHIFT_PCMP(PAT *pat1, PAT *pat2)

   {

    int dsh;

   

    dsh=MinShift[pat2->loc]-MinShift[pat1->loc];

    return(dsh ? dsh : (pat2->loc-pat1->loc));

   }

   

   

   /* Constructs the delta 1 shift table from a pattern string. */

   void BUILD_TD1(char *x, int m, int *td1)

   {

    int a, j;

   

    for (a=0; a < ASIZE; a++) td1[a]=m+1;

    for (j=0; j < m; j++) td1[x[j]]=m-j;

   }

   

   

   /* Find the next leftward matching shift for the first ploc pattern */

   /*  elements after a current shift or lshift.                       */

   int MATCHSHIFT(char *x, int m, int ploc, int lshift, PAT *pattern)

   {

    int i, j;

   

    for (; lshift < m; lshift++) {

       i=ploc;

       while (--i >= 0) {

          if ((j=(pattern[i].loc-lshift)) < 0) continue;

          if (pattern[i].c != x[j]) break;

       }

       if (i < 0) break;

    }

    return(lshift);

   }

   

   

   /* Constructs the delta2 shift table from an ordered string. */

   void BUILD_TD2(char *x, int m, int *td2, PAT *pattern)

   {

    int lshift, i, ploc;

   

    td2[0]=lshift=1;

    for (ploc=1; ploc <= m; ploc++) {

       lshift=MATCHSHIFT(x, m, ploc, lshift, pattern);

       td2[ploc]=lshift;

    }

    for (ploc=0; ploc <= m; ploc++) {

       lshift=td2[ploc];

       while (lshift < m) {

          i=pattern[ploc].loc-lshift;

          if (i < 0 || pattern[ploc].c != x[i]) break;

          lshift++;

          lshift=MATCHSHIFT(x, m, ploc, lshift, pattern);

       }

       td2[ploc]=lshift;

    }

   }

   

   /* Maximal Shift string matching algorithm. */

   void MS(char *y, char *x, int n, int m)

   {

    int i, j, td2[XSIZE], td1[ASIZE];

    PAT pattern[XSIZE];

   

    /* Preprocessing */

    COMPUTE_MINSHIFT(x ,m);

    ORDER_PATTERN(x, m, MAXSHIFT_PCMP, pattern);

    BUILD_TD1(x, m, td1);

    BUILD_TD2(x, m, td2, pattern);

   

    /* Searching */

    i=0;

    while (i <= n-m) {

       j=0;

       while (j < m && y[i+pattern[j].loc] == pattern[j].c) j++;

       if (j >= m) OUTPUT(i);

       i+=MAX(td1[y[i+m]], td2[j]);

    }

   }