对于一个有限自动机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得知：p0...4==s0...4，p0...1==p3...4=="ab"，当s5与p5无法匹配时，可以尝试判断s5==p2是否成立，若成立，由前面的推论可知p0...1,2==s3...4,5，所以第5个字符匹配失败时，可以将p的索引回退到2继续进行比较，这样就无需变动s的索引，节约了计算时间，所以只要能够为状态机设计出合理的状态转移函数，就能够加速字符串的匹配。
更一般化情况下，对于模式串p0...m-1，待匹配字符串s0...n-1，对任意i∈0,m-1,j∈0,n-1，有：i,j=δ(i,pj) ( i 为状态机当前状态索引，j 为 s 的索引)。对于δ函数，当循环输入一个字符 pj 时有两种结果，即匹配成功和匹配失败。若匹配成功，i 向后移一位，继续与pj+1进行比较；若匹配失败，则需要将 i 进行跳转，原因后面会解释，这里令 i 的跳转表为 next0...m-1，每次跳转后需重新比较pi与sj，直到它们相等或者i==0时终止跳转，最后再进行一次比较，若相等则 i 可以向后移一位继续与 sj+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
AI 代码解读
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
AI 代码解读
前面的模式串p="abaabcb"在第5个字符匹配失败时，因为有p0...4==s0...4，p0...1==p3...4==ab，所以 i 可以回退到2继续进行匹配，这里的 "ab" 我称为p0...4和pk...5的最长公共前缀，其长度记为 π，满足：
π[i] = max{ k : p[0...k-1]==p[i-k...i-1] ∧ k < i }
AI 代码解读
由上式可推 πi+1=max{k:p0...k-1==p(i+1)-k...(i+1)-1∧k<(i+1)}，π0=0，令 πi=x：
1)当pi==px时，总有 p0...x-1px==pi-x...i-1pi，即p0...(x+1)-1==p(i+1)-(x+1)...(i+1)-1，可得πi+1==x+1= =πi+1，因此，对任意pi==p[πi]，满足递推式：πi+1==πi+1。
2)当pi !=px时，p0...x-1px==pi-x...i-1pi 显然不成立，那么有没有更短的长度为y(y<x)的公共前缀使 p0...y-1py ==pi-y...i-1 成立呢？这里我同样可以对 px 进行状态转移，令y=πx，由于y是x位置的最长公共前缀的长度，所以有 p0...y-1 ==px-y...x-1，又p0...y-1是p0...x-1的最长前缀，所以p0...y-1也是pi-x...i-1的最长前缀，因此满足：πi+1=πx。
从上面的结论来看，π数组跟next数组是有紧密联系的，它们都完成匹配过程中的状态转移，但是却有些细微的区别，不少网络平台上分享的KMP算法在我看来都是有瑕疵的。考虑这样一种情况，在 π 数组已经计算好的前提下，当pi!=sj，需要将 i 移至 πi，令 k=πi，若 pk==pi，那么再比较pk与sj是没有意义的，因此将这样的情况迭代优化后，就能得到 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>
AI 代码解读
分析伪代码不难得知该算法的时间复杂度是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;
}
AI 代码解读
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;
}
AI 代码解读
测试用例：
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;
}
AI 代码解读
