code

Maximal Shift

The Maximal Shift algorithm
ms.c

typedef struct patternScanOrder {
   int loc;
   char c;
} pattern;

int minShift[XSIZE];

void computeMinShift(unsigned char *x, int m) {
   int i, j;
   for (i = 0; i < m; ++i) {
      for (j = i - 1; j >= 0; --j)
          if (x[i] == x[j])
             break;
      minShift[i] = i - j;
   }
}

void orderPattern(unsigned char *x, int m, int (*pcmp)(), pattern *pat) {
   int i;
   for (i = 0; i < m; ++i) {
      pat[i].loc = i;
      pat[i].c = x[i];
   }
   qsort(pat, m, sizeof(pattern), pcmp);
}

void preQsBc(unsigned char *x, int m, int qbc[]) {
   int i;
   for (i=0;i<SIGMA;i++)   qbc[i]=m+1;
   for (i=0;i<m;i++) qbc[x[i]]=m-i;
}

int matchShift(unsigned char *x, int m, int ploc, int lshift, pattern *pat) {
   int i, j;
   for (; lshift < m; ++lshift) {
      i = ploc;
      while (--i >= 0) {
         if ((j = (pat[i].loc - lshift)) < 0)  continue;
         if (pat[i].c != x[j]) break;
      }
      if (i < 0) break;
   }
   return(lshift);
}

void preAdaptedGs(unsigned char *x, int m, int adaptedGs[], pattern *pat) {
   int lshift, i, ploc;

   adaptedGs[0] = lshift = 1;
   for (ploc = 1; ploc <= m; ++ploc) {
      lshift = matchShift(x, m, ploc, lshift, pat);
      adaptedGs[ploc] = lshift;
   }
   for (ploc = 0; ploc <= m; ++ploc) {
      lshift = adaptedGs[ploc];
      while (lshift < m) {
         i = pat[ploc].loc - lshift;
         if (i < 0 || pat[ploc].c != x[i])
            break;
         ++lshift;
         lshift = matchShift(x, m, ploc, lshift, pat);
      }
      adaptedGs[ploc] = lshift;
   }
}


int maxShiftPcmp(pattern *pat1, pattern *pat2) {
   int dsh;
   dsh = minShift[pat2->loc] - minShift[pat1->loc];
   return(dsh ? dsh : (pat2->loc - pat1->loc));
}

int search(unsigned char *x, int m, unsigned char *y, int n) {
   int i, j, qsBc[SIGMA], adaptedGs[XSIZE], count;
   pattern pat[XSIZE];

   /* Preprocessing */
   computeMinShift(x ,m);
   orderPattern(x, m, maxShiftPcmp, pat);
   preQsBc(x, m, qsBc);
   preAdaptedGs(x, m, adaptedGs, pat);

   /* Searching */
   count = 0;
   j = 0;
   while (j <= n - m) {
      i = 0;
      while (i < m && pat[i].c == y[j + pat[i].loc])  ++i;
      if (i >= m)
         OUTPUT(j);
      j += MAX(adaptedGs[i], qsBc[y[j + m]]);
   }
   return count;
}