KMP算法--Next数组原理、代码实现

https://www.cnblogs.com/tangzhengyue/p/4315393.html  非常详细

1. next数组的含义：

KMP是在一个母字符串中查找一个子字符串的高效算法。它可以在匹配过程中失配的情况下，有效地多往后面跳几个字符，加快匹配速度。 

KMP算法中有个数组，叫做前缀数组，也有的叫next数组，每一个子串有一个固定的next数组，它记录着字符串匹配过程中失配情况下可以向前多跳几个字符。当然它描述的也是子串的对称程度，程度越高，值越大，当然之前可能出现再匹配的机会就更大。

2.next数组的求解方法

第一位的next值为0，第二位的next值为1，后面求解每一位的next值时，根据前一位进行比较。首先将前一位与其next值对应的内容进行比较，如果相等，则该位的next值就是前一位的next值加上1；如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。

3.next数组实现

void SetPrefix(char[] P, int prefix[])

{

     int len=P.length;//模式字符串长度。

     prefix[0]=0;

     for(int i=1; i<len; i++)

     {

         int k=prefix[i-1];

         //不断递归判断是否存在子对称，k=0说明不再有子对称，Pattern[i] != Pattern[k]说明虽然对称，但是对称后面的值和当前的字符值不相等，所以继续递推

         while( Pattern[i] != Pattern[k]  &&  k!=0 )               

             k=prefix[k-1];     //继续递归

         if( Pattern[i] == Pattern[k])//找到了这个子对称，或者是直接继承了前面的对称性，这两种都在前面的基础上++

              prefix[i]=k+1;

         else

              prefix[i]=0;       //如果遍历了所有子对称都无效，说明这个新字符不具有对称性，清0

     }

}