code

TVSBS

The TVSBS algorithm
tvsbs.c

void TVSBSpreBrBc(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 count,i,j =0;
   int BrBc[SIGMA][SIGMA];
   unsigned char firstCh, lastCh;
   count = 0;
   TVSBSpreBrBc(x, m, BrBc);
   firstCh = x[0];
   lastCh = x[m -1];
   for (i=0; i<m; i++) y[n+i]=y[n+m+i]=x[i];
   while(j <= n - m){
      if (lastCh == y[j + m - 1] && firstCh == y[j]) {
         for (i = m-2; i > 0 && x[i] == y[j + i]; i--);
         if (i <= 0) count++;
      }
      j += BrBc[y[j + m]][y[j+m+1]];
   }
   return count;
 }