code

SSABS

The SSABS algorithm
ssabs.c

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

 ////////////Searching Phase///////////////////////////////////////
 int search(unsigned char *x, int m, unsigned char *y, int n){
   int count,i,j =0;
   int qsBc[SIGMA];
   unsigned char firstCh, lastCh;
   count = 0;
   preQsBc(x, m, qsBc);
   firstCh = x[0];
   lastCh = x[m -1];
   for (i=0; i<m; i++) y[n+i]=lastCh;
   while(j <= n - m){
     // Stage 1
     if (lastCh == y[j + m - 1] && firstCh == y[j])
     {
        //Stage 2
        for (i = m-2; i > 0 && x[i] == y[j + i]; i--);
        if (i <= 0) count++;
     }
     // Stage 3
     j += qsBc[y[j + m]];
    }
    return count;
 }