1、先求 next 数组：
// pattern 是模式串，n 是串长度
void kmpnext(string pattern, int next[], int n) {
next[0] = -1;
int k = -1;
int j = 1;
while(j < n) {
if(pattern[j-1] == pattern[k] || k == -1) {// 这个 k 指的是上一轮的 next 值，即 next[j-1]
next[j++] = ++k;
}
else { // 这里 k 会递归找 j - 1 的 next 值 的 next 值......，直到进入上面那个 if 中
k = next[k];
}
}
}
2、利用 next 数组进行 KMP 算法匹配：
// text 是原串，pattern 是模式串，tL 是原串长度，pL 是模式串长度
int kmp(string text, string pattern, int tL, int pL, int next[]) {
int i = 0, j = 0;
while(i < tL && j < pL) {
if(text[i] == pattern[j]) { // 如果相等，两个一起后移
i++;
j++;
}
else if(j != 0){ // 如果不相等且非模式串第一个字符，i 不动，j 找 next
j = next[j];
}
else { // 如果不相等且是模式串第一个字符，i 后移
i++;
}
}
if(j == pL) { // 如果 j 走到最后，说明模式串每个字符都匹配过
return i - pL;
}
return -1;
}
3、测试
int main()
{
string text = "ACBABE";
string pattern = "BE";
int tL = text.length();
int pL = pattern.length();
int next[pL];
kmpnext(pattern, next, pL);
for(int i = 0; i < pL; i++) // 打印 next 数组
cout << next[i] << " ";
cout << endl;
cout << "index = " << kmp(text, pattern, tL, pL, next);
return 0;
}
捕获.PNG
