模式匹配算法的代码只有十四行，看了两天，终于看懂了，吐槽一下，算法太经典了。
首先要了解一下串操作中模式匹配算法的作用是什么，简单的说就是从一个主串中需找特定的字符子串，要寻找的字符子串称为模式串。自然很容易想到一个方法就是：直接拿模式串在主串中移动，一旦移动到某一个位置模式子串所有的字符与主串中的字符都相同，那么就找到了字符串，该方法成为FM算法。记主串为s1s2……sn，模式串为p1p2……pm。如图一所示：
图一：FM算法串匹配
这种算法很简单，但是时间上付出了很大的代价，每一次匹配不成功，都必须回溯到原来的位置的下一个位置重新匹配，复杂度为O(m*n)。模式串匹配是在该方法的基础之上进行改进，想办法不需要在主串中回溯，即希望主串中每个字符值匹配一次，KMP算法是可以做到的，下面我们就来看看KMP。
假设拿模式串和主串进行匹配，从模式串的第一个字符开始，如果相等，则进行下一个字符的比较……一直进行下去直到两个字符不等，记录此时主串位置为i，模式串位置为j，即第i和第j个位置失配。这样我们想办法让主串的i保持不回溯，其实如果’pj-k+1pj-k+2……pj-1’=’p1p2……pk-1’（在j之前：前缀=后缀，注意这里前后缀相等的长度要取最大值），只需将模式串右移，（令next[j]=k）就可以保持i不回溯了（注意这里我们讨论从第一个字符串开始，不考虑0下标的数组）。如图二所示：
图二：KMP模式串匹配
总结起来KMP算法与FM算法的不同就是，FM在失配时需要回溯，而KMP在i-j失配时不需要回溯，只需确定新的k，使得下一次next[j]=k，重新进行匹配，一直这样下去……确定k的准则就是j之前的：前缀等于后缀pj-k+1pj-k+2……pj-1’=’p1p2……pk-1’。
下面就来谈谈模式串如何用代码实现前缀等于后缀找next[j]=k。请跟上节奏，有点绕：
因为每一个位置都有一个next值，于是可以做如下假设：设模式串第i个位置的next[j]=k，即有：
‘pj-k+1pj-k+2……pj-1’ = ’p1p2……pk-1’ （1）
接下来看一下next[j+1]如何取值？
1）如果pj=pk，则表明
’pj-k+1pj-k+2……pj-1pj’ = ’p1p2……pk-1pk’ （2）
所以next[j+1]= next[j]+1= k+1
2）如果pj != pk，则表明
‘pj-k+1pj-k+2……pj-1’ = ’p1p2……pk-1’ （3）
pj != pk （4）
用下图不同颜色表示相等的前缀和后缀
图三 ：模式串示意图
这时候主模式串又可以看做自己的模式串，即拿自身的前缀去找相同的后缀。由于已经有（3）和（4）式成立。要从图三种找到和后缀2段相同的1段，要知道在图中绿色部分是相同的子串，所以我们要拿p1p2……pnext[k]去与2段匹配（注意1段和3段黑色代表临界的值，不相等，故可以拿1段去与2段匹配），是不是有点绕，就这个地方，好好想想，想清楚了接下来就简单了。这个地方就是一个经典的递推过程。总结起来就是需要找next[k]，此时：
next[j+1]=next[k]+1，
得到next[j+1]之后重复以上所有过程。
当然有可能我们找不到next[k]，那么直接让模式串右移一位就行了，即next[j+1]=1。
C++代码实现过程如下：
void get_next(HString S, int next[])
{//注意下标[1]开始
int i=1;
next[1]=0;//其实这就相当于是递推截止条件
int j=0;
HString subs1, subs2;
while(i<S.StrLength())
{
S.SubString(subs1,i,1);//第i个字符
S.SubString(subs2,j,1);//第j个字符
if(j==0 || subs1.StrCompare(subs2)==0)
{//如果两个字符相等
i++;
j++;
next[i]=j;
}
else
j=next[j];//其实这就是一个递推过程
}
}
KMP算法的改进
上面定义的next尚有缺陷，因为如果模式’aaaab’(next[j]为01234）在和主串’aaabaaaab’匹配时，当i=4,j=4时失配，由next[4]=3可知i=4,j=3、i=4,j=2、i=4,j=1都要进行匹配，但实际上模式串中第1,2,3个字符和第4个字符都想等，因此不需要再和主串中的第4个字符相比较，而可以将模式一次向右直]接滑动4个字符的位置进行i=5，j=1时的字符比较。
这就是说，如果按照之前的定义next[j]=k，而模式中pj=pk，则主串中字符si和pj比较不等时，不需要再和pk进行比较，而可以直接和pnext[k]进行比较。换句话说，此时的next[j]应该和next[k]相同。
改进KMP代码实现如下
void get_next(HString S, int next[])
{//注意下标[1]开始
int i=1;
next[1]=0;//其实这就相当于是递推截止条件
int j=0;
HString subs1, subs2;
while(i<S.StrLength())
{
S.SubString(subs1,i,1);//第i个字符
S.SubString(subs2,j,1);//第j个字符
if(j==0 || subs1.StrCompare(subs2)==0)
{//如果两个字符相等
i++;
j++;
S.SubString(subs1,i,1);//第i++个字符
S.SubString(subs2,j,1);//第j++个字符
if(subs1.StrCompare(subs2)!= 0)
next[i]=j;//由上面的j++，next[i]=k+1
else
next[i]=next[j];//这一步非常经典，其实如果先执行外层的else然后再进入外层if中
//执行内层if，所做的工作非常类似，也是一个递推过程。
}
else
j=next[j];//这就是一个递归过程
}
}