【给数学糟糕的人的KMP】字符匹配教程（一）next数组的理解

【给数学不好的人的KMP】字符匹配教程（一）next数组的理解

    终于接触了一丁点字符匹配的东西（其实也只是入门的KMP），话说这个东西的确需要很强的数学思维，其中NEXT数组尤其坑爹，很多ACMER就是栽在了这个数组上，不明觉厉。什么诸如“失配” “数组移位”和一些S(i-1)...之类的一长串字母的确让我们十分不爽。更有博客表示这个确实很难，此中有真意，欲辨已忘言云云。。算法导论上的模板是从1开始的，自己还写了个SString数据类型让好多人云里雾里，今天我们就来试着解释一下KMP的基本原理吧。

    字符匹配的基本问题是寻找子串在一长串中的位置。比如

一长串s：abacababt

      子串t：abab，返回值就是4.当然你要非说5也行。。

寻找这种东西的位置，最先想到的思路自然是暴搜。。我们用i来表示大串中当前查找的位置，j表示子串中当前查找的位置，开始都是0，然后开搜，条件很简单，s[i]==t[j]。。。

原理见图，

代码如下：

这个数组可以使用搜索的方法得到。网上的教程质量参差不齐，这里给出一个能用的。下标从0开始，next[0]默认为0，获得的数组可以使用调试功能查看。
int next[1000];void build_next(string b){ int i,j=0,key=0;    memset(next,0,sizeof(next));    for(i=1;i<b.size();i++)    {        j=next[i-1];        while(j==1 && b[i]!=b[j])        {        j=next[j-1];        }        if(b[j]==b[i])        {            next[i]=j+1;        }        else next[i]=0;    }}

这个数组的理解与否是掌握KMP的关键，具体怎么使用，下篇文章会给出更新。
1楼shihui142857昨天 23:14
这么关键的算法next_build()都没有个注释吗？
Re: mig_davidli昨天 09:35
回复shihui142857n就是先将next置0（网上的教程版本有两种，一种是next[0]=0,next[1]=1,next[2]=其他..另一种是next[0]=-1,next[1]=0,next[2]=其他...我的是next[0]=0,next[1]=0..）n第一行是j的初始化，J的意思是根据前面已知的next值来判断新加的那一个字符是否相等，不等则回溯。nwhile()的作用是说如果找到相同的一个前缀和后缀字符，则根据前面的next[j]值来判断是加一还是置零。n后面的两个判断是表明了next[j+1]和next[j]的关系，只有两种，要么加一，要么置零。就是说 一个确定的字符串加入一个字母之后，要么匹配的更多了，要么完全不匹配了。