必懂kmp

看毛片算法其实并不难，但是很多人就是看完书还是不懂，觉得难以理解。。。

觉得很多都讲得都长篇大论，没能让人很清晰的接触到核心，下面力求精炼的讲清楚怎么看毛片

基本思想如图：

必懂kmp - JW - JWs blog

我们看匹配的过程

T_i-j......T_i.........

P₀.......P_j...

（留意是匹配了j个字符，匹配到第j+1个字符）

当匹配到T_i和P_j时，T_i != P_j，那么就要移动模式串了，而我们这时知道的信息有：

T_i-j......T_i-1 == P₀.......P_j-1 （j个字符相等） -------------［1］

我们设下一个要和Ti进行比较的字符是Pk（就是说移动了j-k个位），那么前提是

P₀......P_k-1 == T_i-k....T_i-1 （k个字符相等）-------------［2］

满足这个条件的k可能不止一个，我们肯定要选择最大的k，这样才不会漏掉可能的情况

然后联立［1］［2］两条式子，有：

P₀......P_k-1 == P_j-k.......P_j-1 （k个字符相等）-------------［3］

由［3］可以看出，前k个字符和后k个字符相等，就是说，我们可以从模式串本身去得到这些移动的信息，而这个信息就是：

对于P_j失配时，在字串P₀....P_j-1中，有最大的k，使前k个字符和后k个字符相等，k<=j-1，P_k!=P_j

我们设k=next[j]，即next[j]代表P₀....P_j-1中的最大的k（P_j失配时，下一个应该和T_i比较的是P_next[j]）

明显，我们有基本情况：

• j==0
  next[j] = -1

• j==1 //这个情况其实是用下边的规则统一递推出来，写上去只是容易理解清晰一点
  P_j != P_j-1 next[j] = 0
  P_j == P_j-1 next[j] = -1

然后就是递推的关系，这个关系就是看毛片的难点所在，因为这个递推关系不是单纯和其他的next值有关，而是要用一个变量，记录P₀....P_j-1中最大的k，使前k个字符和后k个字符相等，k<=j-1，且P_k!=P_j，因为最后的这个条件，所以我们不能直接用之前的next去推导。设那个记录的变量是i，那么我们有如下的关系：

• P_j+1==P_i+1 ++i , ++j; //++i是更新相等的前后缀的长度
  next[j] = next[i];

• P_j+1!=P_i+1 ++i,++j;
  next[j] = i;
  do
  i=next[i]; //保证了P_next[i] != P_i
  while(i>=0 && P_j != P_i);

第一条规则，因为条件，明显就有next[j]=next[i]

第二条规则，也是因为条件，明显有next[j]=i，难点在于更新i的值

结合这些条件，我们就可以写出球next数组的函数了

void getnext(char  *P,int  *next)
{
    int len = strlen(P),i=-1,j=0;
    next[0]  =  -1; 

    while(j<len)  {
        ++j;++i;
        next[j]  = i;
        if(P[i]==P[j])  next[j]  =  next[i];
        while(i>=0  && P[j]!=P[i]) i =  next[i];
    }   
}

next数组都搞定了，搜索没什么好说了的