匹配
很简单，用next[x]表示前移数组。
// 伪代码
while(!complete()) {
if(match(c[i], str[j]))
i++,j++;
else
i = next[i];
}
return j+1-len(c);
next[i]的生成
匹配过程事实上非常简单，难的是next[x]的生成。
思路：用两个迭代器，递归思想。
记号：用c[x]表示待处理字符串，用next[x]表示前移数组。
朴素next生成算法
这样求出来的next[x]有以下性质：
-
c[0]=>c[next[x-1]]的字符串匹配c[x-1-next[x-1]]=>c[x-1]的字符串 -
next[x]是满足以上条件的最大值
从这一表达式可以看出，next[x]从数学上难以直观求解。
注：有人使用“前缀”“后缀”来表示1.条件，令人十分不习惯，还需要进一步翻译成数学语言，太不直接
使用两个迭代器i,k其中i在前，k在后。每一次迭代的结果是求出next[i+1]。上一次迭代之后，显然i=i+1，k应当满足：
- 处于这样一个位置，即“从
c[0]到c[k]的字符序列完全匹配从c[i-k]到c[i]的字符序列”。比如，"abab"k=2, i=4或者"aaaa"k=3,i=4。容易验证，空串(k=-1,i=0)满足这个状态。 - k是满足条件1.的最大可能值。
满足这一条件时，考虑next[i+1]，可见直接让next[i+1]=k+1，我们便满足了next[x]的两条性质。且慢！这里要使递归进行下去，还要使末态满足下面两条性质。怎么做呢？
若c[i+1]==c[k+1]是最皆大欢喜的事情。这时k=k+1自然满足条件。次好的事情是k==-1，如果c[i+1]==c[0]不满足，只要继续让k=-1就好了。不然的话怎么弄呢？需要减少匹配的字符数。本质上，这又是一个c与自己的匹配！这么考虑：“从c[0]到c[k]的字符序列完全匹配从c[i-k]到c[i]的字符序列”，c[i+1]==c[k+1]不满足。于是移动c，从下一个可能的匹配位置开始匹配，直到“从c[0]到c[k']的字符序列完全匹配从c[i+1-k']到c[i+1]的字符序列”.
// 循环内部
next[i+1]=k+1;
if(c[k+1]==c[i+1])
k++;
else {
if(k==-1)
// 什么也不做
else {
k = k+1-KMP(c, c+i-k); // 伪代码，被匹配者最大到c+i+1
}
}
i++;
// 上面伪代码事实上包括了特殊情况，自行验证一下！
// 循环内部
next[i+1]=k+1;
k = k+1-KMP(c, c+i-k);
i++;
我们试着把匹配过程写开。
next[i+1]=k+1;
m=0, n=0;
while(true) {
if(c[m]==c[i-k+n]) {
/* if(m>i) break; */ //不可能发生
if(n>k+1) break; // n==k+2
m++,n++;
}
else {
m=next[m];
if(m==-1) break;
}
}
// k=k+1-((k+2)-(m+1))
k=m;
i++;
这种写法未免过于复杂。事实上，第一趟匹配中，c[0=>k]其实都是匹配好的。可以借此简化代码：
next[i+1]=k+1;
m=k+1, n=k+1;
while(m!=-1 && n<=k+1) {
if(c[m]==c[i-k+n])
m++,n++; // 事实上循环直接跳出了
else
m=next[m];
}
k=m;
i++;
我们发现变量n其实是多余的。
next[i+1]=k+1;
m = k+1;
while(m>=0 && c[m]!=c[i+1])
m=next[m]; // k=next[k+1]-1
k=m;
i++;
m也是多余的。把上面的代码改写一下，成为如下简单形式：
while(k>=0 && c[k]!=c[i])
k=next[k];
i++,k++;
next[i]=k;
优化的next生成算法
next数组满足的条件为：
-
c[0]=>c[next[x-1]]的字符串匹配c[x-1-next[x-1]]=>c[x-1]的字符串 c[x]!=c[next[x]]-
next[x]是满足以上条件的最大值
上面的算法脑抽了，要想匹配少，显然k越小越好。比如，要匹配"abababac"，仅考虑前5位，next[5]应该为3. 但第6位b不匹配，第4位b也不可能匹配。这就其实可以进一步减小k的值，只需要加一个判断：
while(k>=0 && c[k]!=c[i])
k=next[k];
i++,k++;
if(c[i]==c[k])
next[i]=next[k];
else
next[i]=k;
用数学归纳法可以证明，优化的这一算法生成的next[x]满足上面三点条件。
完整代码(C语言)
// KMP
#define MAX_LEN 50
typedef struct
{
char c[MAX_LEN];
int n;
} SeqString, *pSeqString;
void makeNext(pSeqString p, int next[])
{
int i = 0, k = -1;
next[0] = -1;
while (i < p->n - 1)
{
while (k >= 0 && p->c[i] != p->c[k])
k = next[k];
i++;
k++;
// next[i] = k;
if (p->c[i] == p->c[k])
next[i] = next[k];
else
next[i] = k;
}
}
int pMatch(pSeqString t, pSeqString p, int next[])
{
int i = 0, j = 0;
while (i < p->n && j < t->n)
if (i == -1 || p->c[i] == t->c[j])
{
i++;
j++;
}
else
i = next[i];
if (i >= p->n)
return (j - p->n + 1);
else
return 0;
}
扩展
KMP算法的匹配，思想和“状态机”有一定的相似性。两个迭代器对应的字符进行比较，失败则改变一下“状态”，改变的方式由next[x]数组定义。KMP算法的一种进阶形式是AC自动机算法，可以处理更加复杂的多维匹配问题。
