code

Backward SNR DAWG Matching

The Backward SNR DAWG Matching algorithm
bsdm6.c

#define DSIGMA 65536
#define HS(x,i) (x[i]<<5) + (x[i+1]<<4) +  (x[i+2]<<3) + (x[i+3]<<2) + (x[i+4]<<1) + x[i+5]
#define Q 6

int search(unsigned char *x, int m, unsigned char *y, int n) {
unsigned int B[DSIGMA];
int i, j, k, count;
    unsigned int s,d;
if (m<Q) return -1;

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

/* 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) {
    c = HS(y,j);
    while ((i=pos[c])<0) {
        j+=len;
            c = HS(y,j);
    }
    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;
}