字符串匹配算法 - KMP

KMP 算法由 KMP 主程序和求解 next 数组子程序构成(在以下代码中记为 $f$)。$f$ 又可以理解为一个状态转移自动机,当匹配失败时转移模式串指针。

需要注意的是,标准KMP算法中求解 $f$ 的过程有一个优化(作用略):

f[i] = p[i] == p[j] ? f[j] : j;

该优化可以显著减少 KMP 主程序的执行时间,然而在利用 $f$ 数组计算字符串的周期性时,不可使用优化版的求解方式,只能使用原始转移方式:

f[i] = j;

KMP 算法的整体模板如下:

KMP.cppview raw
#include <iostream>
#include <stdio.h>
#include <cstring>
#define maxn 105
using namespace std;

int f[maxn];

void getf(char *p) {
int len = strlen(p);
memset(f, -1, sizeof f);
for (int i = 0, j = -1; i < len;) {
while (~j && p[i] != p[j]) j = f[j];
i++; j++;
f[i] = p[i] == p[j] ? f[j] : j;
}
}

int kmp(char *t, char *p) {
int len = strlen(t), lenp = strlen(p);
getf(p);
for (int i = 0, j = 0; i < len;) {
while (~j && t[i] != p[j]) j = f[j];
i++; j++;
if (j == lenp) {
return i - j;
// j = 0;
}
}
return -1;
}

int main() {
char t[100], p[10];
cout << kmp(t, p);
return 0;
}