code

Backward SNR DAWG Matching

The Backward SNR DAWG Matching algorithm
bsdm.c


int search(unsigned char *x, int m, unsigned char *y, int n) {
unsigned int B[SIGMA];
int i, j, k, count;
    unsigned int s,d;

/* Preprocessing */
    unsigned int occ[SIGMA] = {0};
    int start = 0, len = 0;
    for (i=0, j=0; i<m; i++) {
        if (occ[x[i]]) {
            while(x[j]!=x[i]) {
                occ[x[j]]=0;
                j++;
            } 
            occ[x[j]]=0;
            j++;
        }
        occ[x[i]]=1;
        if (len < i-j+1 ) {
            len = i-j+1;
            start = j;
        }
    }
unsigned int pos[SIGMA];
for (i=0; i<SIGMA; i++) pos[i]=-1;
for (i=0; i<len; i++) pos[x[start+i]]=i;

    //printf("%d / %d\n",m,len);
    //for (i=start; i<start+len; i++) printf("%d ",x[i]);
    //if (start+len<m) printf("[%d] ",x[start+len]);
    //printf("\n\n");

/* Searching */
for (i=0; i<m; i++) y[n+i]=x[i];
unsigned char *xstart = x+start;
int offset = len+start-1;
j = len-1;
while(j<n) {
    while ((i=pos[y[j]])<0) j+=len;
    k=1;
    while(k<=i && xstart[i-k]==y[j-k]) k++;
    if (k>i) {
     if (k==len) {
     if (!memcmp(x,y+j-offset,m)) if (j-offset<=n-m) count++;
     }
     else j-=k;
    }
    j+=len;
}
    return count;
}