KMP匹配算法源码
模式匹配问题，即字符串的匹配，int index(String t,String p)，求p在t中第一次出现的位置。如何高效地匹配？先来讨论朴素的回溯的模式匹配。例如，设t=“abbaba”，p=“aba”，t的长度为6（plen=6），t的长度为3（tlen=3）。匹配过程如下：
算法如下：
int index(string p, string t)
{
int i = 0, j = 0; //i，j分为p，t串当前字符的下标
while(i<p->n && j<t->n){ //反复比较
if(p->c[i] == t->c[j]){
i++; j++; //继续匹配下一个字符
}
else{
j = j - i + 1; //p，t串的i，j回溯，即重新开始下一次匹配
i = 0;
}
}
if(i >= p->n)
return(j - i +1); //匹配成功，返回p中第一个字符在t中的序号
else
return 0; //匹配失败
}这种算法效率不高，在最坏的情况下，每趟比较都在最后出现不等，最多比较 tlen-plen+1 趟，总比较次数为 plen×（tlen-plen+1），由于在一般情况下plen<<tlen，所以算法的运行时间为O（plen× tlen）。
对于上图的匹配过程，由（a）可知：p0=t0，p1=t1，p2！=t2，
由p0！=P1可知p0！=t1，将p右移一位后（b）的比较一定不等；
由p0==p2可知p0！=t2，将p再右移一位后（c）的比较一定不等；
因此，由（a）便可直接将p右移3位跳到（d），从p0和t3开始作比较，很快可以匹配成功。这样的匹配过程对字符串 t 就消除了回溯。
这种快速的算法也就是，在右移若干位后，立即用p串中的一个新的字符Pk（k<i）和tj（甚至t（j+1））继续作比较。Knuth等人发现这个k值不仅存在，而且仅依赖于p串本身，与t串无关，因此可以在与任何串匹配前计算出k值。
假设k值已经存在，存放在数组next中，next[ i ] 表示与pi对应的k值。意义就是，一旦匹配过程中发现pi！=tj，可用p中以next[ i ]为下标的字符Pnext[ i ] 与tj作比较。特别地，当p中任何字符都不能和tj比较时（此时next[ i ]==0），直接从t（j+1）和p0作比较。将上面的算法部分改变：
while(i<p->n && j<t->n){
if(i == -1){
i++; j++; //i变为0，即t(j+1)和p0作比较
}
else if(p->c[i] == t->[j]){
i++; j++;
}
else
i=next[i];
} while(i<p->n && j<t->n){
if(i == -1 || p->c[i] == t->[j]){
i++; j++; //i变为0，即t(j+1)和p0作比较
}
else
i=next[i];
}那么怎样计算next数组呢？
我们发现，在p与任意目标t匹配时，若pi≠tj，则意味着pi之前的字符已与t中对应的字符相等。因此，如下图(a)和(b)是等价的。
然后，将p右移i-k位，希望用pk与tj继续比较，这意味着tj以前的比较工作都已全部相等，相当于p0…p(i-1)的一个前缀p0…p(k-1)与它的一个后缀p(i-k)…p(i-1)长度相等。如图，
因此，在p0…p(i-1)中，求出其相同的而且是最长的前缀和后缀，设长度为k(0≤k≤i-1)，这个值仅仅依赖于p本身，与任何t无关。
①当右移量为i-k时，相同的前后缀恰好对齐，pk与tj对齐。用不着再去比较这一对相同的前后缀；
②当右移量小于i-k时，也用不着去比较，因为根据k的意义，长度大于k的前后缀必定不相等；
③当右移量大于i-k时，又可能错过匹配成功的机会。
通过上面的分析，可以知道求next数组的关键，就是求出p0…p(i-1)中最大的相同的前后缀的长度。而求出这个长度，也就是判断p0…p(i-2)是否等于p1…p(i-1)，如果不等，则继续判断p0…p(i-3)是否等于p2…p(i-1)等等。显然，这实际上还是模式匹配问题。
作为一种特殊情况，当i=0时，令next[0]=-1，因为p0与tj比较不等，只能用p0与t(j+1)去比较。另外，如果p0…p(i-1)的最大相同的前后缀长度为k，那么p0…pi的最大相同的前后缀长度就为k+1。加上有next[0]=-1的基础，就可以依次计算出next[1]，next[2]…next[n-1]。在计算next[i+1]时，充分利用已经求出的next[0]，next[1]…next[i]的值，使得计算next[i+1]的过程有点类似于前面的无回溯的模式匹配问题。算法如下:
void makeNext(PSeqString p, int *next)
{
int i = 0, k = -1; //初始化
next[0]=-1;
while(i < p->n - 1){ //计算next[i+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;算法分析，从表面上看，有两层循环，每重循环最多执行m次，最大的运行时间可能达到O（m^2），但仔细分析，因为每执行一次最外层循环，i 严格增加1，所以最外层循环正好执行 m-1 次；另外k值从-1开始，执行 k+m-1 次（i++; k++;），并且只有在这一语句中k被增值。在内层循环中，语句k=next[k] 至少使d减少1，所以整个算法中，这个语句执行次数不可能超过m-1次（否则k将小于-1，不可能），所以最内层循环的执行次数最大为 m-1 。
因此，该算法的时间代价为O（m），与无回溯的模式匹配模式合在一起，即用长度为m的模式串p与长度为n的目标串t进行匹配，所需的时间为O（m+n），算法如下：
int index(PSeqString p, PSeqString t, int *next)
{
int i = 0, j = 0; //i，j分为p，t串当前字符的下标
while(i<p->n && j<t->n){
if(i == -1 || p->c[i] == t->[j]){
i++; j++; //i变为0，即t(j+1)和p0作比较
}
else
i=next[i];
}
if(i >= p->n)
return(j - i + 1); //匹配成功，返回p中第一个字符在t中的序号
else
return 0; //匹配失败
}
void makeNext(PSeqString p, int *next)
{
int i = 0, k = -1; //初始化
next[0]=-1;
while(i < p->n - 1){ //计算next[i+1]
while(k >= 0 && p->c[i] != p->c[k])
k=next[k];
i++;
k++;
if(p->c[i] == p->c[k])
next[i] = next[k];
else
next[i] = k;
}
}当n>>m时，该算法的优越性更显然，特别是当一个模式p被反复使用时，只要花一次O（m）的时间代价计算next数组，以后的每次匹配只要用O（n）的时间；但是，当n和m相差不大时，并且只匹配一次就能成功时，朴素的回溯的算法更快。
下面是一个例子的完整代码（部分变量储存方式已改变）：
#include <iostream>
using namespace std;
int index(string p, string t, int lenP, int lenT, int *next)
{
int i = 0, j = 0; //i，j分为p，t串当前字符的下标
while(i<lenP && j<lenT){
if(i == -1 || p[i] == t[j]){
i++; j++; //i变为0，即t(j+1)和p0作比较
}
else
i=next[i];
}
if(i >= lenP)
return(j - i + 1); //匹配成功，返回p中第一个字符在t中的序号
else
return 0; //匹配失败
}
void makeNext(string p, int lenP, int *next)
{
int i = 0, k = -1; //初始化
next[0]=-1;
while(i < lenP - 1){ //计算next[i+1]
while(k >= 0 && p[i] != p[k])
k=next[k];
i++;
k++;
if(p[i] == p[k])
next[i] = next[k];
else
next[i] = k;
}
}
int main()
{
string p, t;
cout<<"Input P string:\n";
cin>>p;
cout<<"Input t string:\n";
cin>>t;
int len = p.length();
int next[len];
makeNext(p, len, next);
cout<<"The begin position is "
<<index(p, t, len, t.length(), next);
}结果样例：
Input P string:
ANOTONY
Input t string:
abcdefANOTONYghijANTONYsfj
The begin position is 7