See the function search
below, it returns count
but I don't see where this variable count
acts/works (the function is found in a library , click here to download the source code, you will find kmp.c
in \source\algos
):
#include "include/define.h"
#include "include/main.h"
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, kmpNext[XSIZE], count;
/* Preprocessing */
BEGIN_PREPROCESSING
preKmp(x, m, kmpNext);
END_PREPROCESSING
/* Searching */
BEGIN_SEARCHING
count = 0;
i = j = 0;
while (j < n) {
while (i > -1 && x[i] != y[j])
i = kmpNext[i];
i ;
j ;
if (i >= m) {
OUTPUT(j - i);
i = kmpNext[i];
}
}
END_SEARCHING
return count;
}
Can any one explain how it works?
CodePudding user response:
The OUTPUT
macro that is defined in ./source/algos/include/define.h
looks like this:
#define OUTPUT(j) count
And in search
you have
if (i >= m) {
OUTPUT(j - i); // <- here
i = kmpNext[i];
}
which explains how count
is updated.