for (int i = 0; i < n; i++) { /* Scan the text from left to right */
while (q > 0 && p[q] != t[i])
q = x[q-1]; /* Next character does not match */
if (p[q] == t[i])
q++; /* Next character matches */
if (q == m) { /* Is all of p matched */
cout<<"Pattern occurs with shift "<<i-m+1<<endl;
q = x[q-1]; /* Look for the next match */
}
}
}
int main() {
char *t = "123abcdefg123hijk123";
char *p = "123";
kmp_matcher(t, p);
return 0;
}
运行结果:
Pattern occurs with shift 0
Pattern occurs with shift 10
Pattern occurs with shift 17
说明:
算法原理参见算法导论第32章
《算法导论》的字符串第一个位置从1开始,为了不浪费空间,这个程序的字符串的第一个位置从0开始,所以:
Pq表示字符串P[0...q-1]
x[q]表示字符串Pq+1的最长后缀的长度