KMP算法的数学原理（优化版）
对于一个有限自动机M，它是一个5元组（S,s₀,A,Σ,δ)，S是有限状态集，s₀是初始状态(x₀∈X)，A是可接受状态集(A⊆X)，∑是有限输入表，δ是状态转移函数(从S×Σ到S的映射)。假定有一个模式串p="abaabcb"(长度m)，待匹配字符串s="abaabaabcb"(长度n)，当第5个字符'c'匹配失败时，寻常的做法是将p的索引回退到0，s的索引回退到1，再重新进行匹配。观察s与p得知：p[0...4]==s[0...4]，p[0...1]==p[3...4]=="ab"，当s[5]与p[5]无法匹配时，可以尝试判断s[5]==p[2]是否成立，若成立，由前面的推论可知p[0...1,2]==s[3...4,5]，所以第5个字符匹配失败时，可以将p的索引回退到2继续进行比较，这样就无需变动s的索引，节约了计算时间，所以只要能够为状态机设计出合理的状态转移函数，就能够加速字符串的匹配。
更一般化情况下，对于模式串p[0...m-1]，待匹配字符串s[0...n-1]，对任意i∈[0,m-1],j∈[0,n-1]，有：[i,j]=δ(i,p[j]) ( i 为状态机当前状态索引，j 为 s 的索引)。对于δ函数，当循环输入一个字符 p[j] 时有两种结果，即匹配成功和匹配失败。若匹配成功，i 向后移一位，继续与p[j+1]进行比较；若匹配失败，则需要将 i 进行跳转，原因后面会解释，这里令 i 的跳转表为 next[0...m-1]，每次跳转后需重新比较p[i]与s[j]，直到它们相等或者i==0时终止跳转，最后再进行一次比较，若相等则 i 可以向后移一位继续与 s[j+1]比较，伪代码如下：
delta(p,s,next,i,j) while i>0 and p[i]!=s[j] i=next[i] if p[i]==s[j] i=i+1 return i
kmp_search(p,s,next) m=p.length n=s.length i,j=0 while i<m and j<n i=delta(p,s,next,i,j) j=j+1 if i==m return j-m return -1
前面的模式串p="abaabcb"在第5个字符匹配失败时，因为有p[0...4]==s[0...4]，p[0...1]==p[3...4]==ab，所以 i 可以回退到2继续进行匹配，这里的 "ab" 我称为p[0...4]和p[k...5](k∈(0,5))的最长公共前缀，其长度记为 π，满足：
π[i] = max{ k : p[0...k-1]==p[i-k...i-1] ∧ k < i }
由上式可推 π[i+1]=max{k:p[0...k-1]==p[(i+1)-k...(i+1)-1]∧k<(i+1)}，π[0]=0，令 π[i]=x：
1)当p[i]==p[x]时，总有 p[0...x-1]p[x]==p[i-x...i-1]p[i]，即p[0...(x+1)-1]==p[(i+1)-(x+1)...(i+1)-1]，可得π[i+1]==x+1= =π[i]+1，因此，对任意p[i]==p[π[i]]，满足递推式：π[i+1]==π[i]+1。
2)当p[i] !=p[x]时，p[0...x-1]p[x]==p[i-x...i-1]p[i] 显然不成立，那么有没有更短的长度为y(y<x)的公共前缀使 p[0...y-1]p[y] ==p[i-y...i-1] 成立呢？这里我同样可以对 p[x] 进行状态转移，令y=π[x]，由于y是x位置的最长公共前缀的长度，所以有 p[0...y-1 ]==p[x-y...x-1]，又p[0...y-1]是p[0...x-1]的最长前缀，所以p[0...y-1]也是p[i-x...i-1]的最长前缀，因此满足：π[i+1]=π[x]。
从上面的结论来看，π数组跟next数组是有紧密联系的，它们都完成匹配过程中的状态转移，但是却有些细微的区别，不少网络平台上分享的KMP算法在我看来都是有瑕疵的。考虑这样一种情况，在 π 数组已经计算好的前提下，当p[i]!=s[j]，需要将 i 移至 π[i]，令 k=π[i]，若 p[k]==p[i]，那么再比较p[k]与s[j]是没有意义的，因此将这样的情况迭代优化后，就能得到 next 数组，满足：
伪代码如下：
compute_next(p,next) next[0]=0 k=0 m=p.length for i = 1 to if p[i]==p[k] next[i]=next[k] k=k+1 else next[i]=k while k>0 k=next[k] if(p[i]==p[k]) k=k+1 goto out <out>
分析以上伪代码后不难得知该算法的算法复杂度是O(m+n)，以下是C语言实现的KMP算法：
#include <string.h>
void compute_next(const char* p, int m, int next[]) {
next[0] = 0;
int k = 0;
for (int i = 1; i < m; ++i) {
if (p[i] == p[k]) {
next[i] = next[k];
++k;
} else {
next[i] = k;
while (k > 0) {
k = next[k];
if (p[i] == p[k]) {
++k;
break;
}
}
}
}
}
int delta(const char* p, const char* s, int next[], int i, int j) {
while (i > 0 && p[i] != s[j]) {
i = next[i];
}
if (p[i] == s[j]) {
++i;
}
return i;
}
int kmp_search(const char* p, const char* s, int m, int n, int next[]) {
int i = 0, j = 0;
for (; i < m && j < n; ++j) {
i = delta(p, s, next, i, j);
}
return i == m ? j - m : -1;
}
delta函数可以合并到kmp_search函数进行简化，如下：
void compute_next(const char* p, int m, int next[]) {...}
int kmp_search(const char* p, const char* s, int m, int n, int next[]) {
int i = 0, j = 0;
for (; i < m && j < n; ++j) {
while (i > 0 && p[i] != s[j]) {
i = next[i];
}
if (p[i] == s[j]) {
++i;
}
}
return i == m ? j - m : -1;
}
测试用例：
int main(int argc, char** argv) {
const char* testStrings[][2] = {
{"tencent", "encentencentabcskf"}, //true
{"alibaba", "ajsdkalibalibabisk"}, //false
{"baidu", "baibai.www.baidu.com"}, //true
{"bytedance", "ajbytedadanceaaa"}, //false
{"google","googoelglegooglegooo"}, //true
{"microsoft","microsofmicrosofp"} //false
};
int count = sizeof(testStrings) / sizeof(testStrings[0]);
const char *p, *s;
int m, n;
for (int i = 0; i < count; ++i) {
p = testStrings[i][0];
s = testStrings[i][1];
m = strlen(p);
n = strlen(s);
int next[m];
compute_next(p, m, next);
int ret = kmp_search(p, s, m, n, next);
if (ret != -1)
printf("模式串'%s'移 %d 位匹配'%s'成功\n", p, ret, s);
else
printf("模式串'%s'与'%s'匹配失败\n", p, s);
}
return 0;
}
