code

Two Sliding Window

The Two Sliding Window algorithm
tsw.c

void preBrBc(unsigned char *x, int m, int brBc[SIGMA][SIGMA]) {
   int a, b, i;
   for (a = 0; a < SIGMA; ++a)
      for (b = 0; b < SIGMA; ++b)
         brBc[a][b] = m + 2;
   for (a = 0; a < SIGMA; ++a)
      brBc[a][x[0]] = m + 1;
   for (i = 0; i < m - 1; ++i)
      brBc[x[i]][x[i + 1]] = m - i;
   for (a = 0; a < SIGMA; ++a)
      brBc[x[m - 1]][a] = 1;
}

int search(unsigned char *x, int m, unsigned char *y, int n) {
   int j, brBc_left[SIGMA][SIGMA], brBc_right[SIGMA][SIGMA];
   int i, a,b;
   int count;
   unsigned char x1[XSIZE];
   for (i=m-1, j=0; i>=0; i--, j++) x1[j]=x[i];

   /* Preprocessing */
   preBrBc(x, m, brBc_left);
   preBrBc(x1, m, brBc_right);
   count =0;

   /* Searching */
   j = 0; a = n-m;
   while (j <= a) {
      for (i=0; i<m && x[i]==y[j+i]; i++);
      if (i>=m && j<=a) count++;

      for (b=0; b<m && x[b]==y[a+b]; b++);
      if (b>=m && j<a) count++;

      j += brBc_left[y[j + m]][y[j + m + 1]];
      a -= brBc_right[y[a - 1]][y[a - 2]];
   }
   return count;
}