code

Apostolico Crochemore

The Apostolico Crochemore algorithm
ac.c

void preKmp(unsigned char *x, int m, int kmpNext[]) {
    int i, j;
    i = 0;
    j = kmpNext[0] = -1;
    while (i < m) {
       while (j > -1 && x[i] != x[j])
           j = kmpNext[j];
       i++;
       j++;
       if (i<m && x[i] == x[j])
           kmpNext[i] = kmpNext[j];
       else
           kmpNext[i] = j;
   }
}


int search(unsigned char *x, int m, unsigned char *y, int n) {
    int i, j, k, ell, kmpNext[XSIZE], count;

    /* Preprocessing */
    preKmp(x, m, kmpNext);
    for (ell = 1; ell<m && x[ell - 1] == x[ell]; ell++);
    if (ell == m) ell = 0;

    /* Searching */
    count = 0;
    i = ell;
    j = k = 0;
    while (j <= n - m) {
        while (i < m && x[i] == y[i + j])   ++i;
        if (i >= m) {
            while (k < ell && x[k] == y[j + k])  ++k;
            if (k >= ell) OUTPUT(j);
        }
        j += (i - kmpNext[i]);
        if (i == ell) k = MAX(0, k - 1);
        else
            if (kmpNext[i] <= ell) {
                k = MAX(0, kmpNext[i]);
                i = ell;
            }
            else {
                k = ell;
                i = kmpNext[i];
            }
    }
    return count;
}