这篇文章适合那些对KMP算法大致已经理解，但是对next数组的计算原理还不太清楚的小伙伴阅读。

先上代码：

next[0] = -1//仅仅是为了编程的方便 含义为第一个字符就匹配不上，那么匹配串和模式串指针都向前移动1个; next[1…] 含义：该字符前面的子串前缀和后缀的最长匹配长度 例如 “abbabc” 中next[2] = 0 ;

对 j = next[j] 理解： 显然两个绿色方框中的内容相同并且长度为j,如果p[j] != p[i] 那么显然此时next[i+1]的值必然要会小于j（即j的指向会向后退，如图2所示）。若图2中j※的指向就是后退的最终位置，则显然有红色方框的内容是相等的，并且此时p[j*] = p[i]也相等。

此时便来到了问题最关键的地方：j应当以何种方式向后退多少步才能满足条件？ 这里对后退的唯一限制条件是：**后退后要使得红色方框的内容得相等！**所以显然不能盲目一个一个向后退，应该利用前面计算好的next值按照一定的规律向后退。这里的规律就是j = next[j]。 接下来我们来说明两个问题：1.为什么后退到next[j]处可以满足红色方框的内容相等。2.后退到next[j]是否会后退的过多（因为我们要求的是最长的前后缀匹配长度），即这个问题讨论的是后退的位置是否是正合适的位置。 先来看第一个问题：由前文中对next[0,1…]含义的说明图3中Q1和Q2部分相等，由图1中S1和S2相等可知图3中Q1=Q2=Q3=Q4。所以Q1=Q4满足后退条件。

再来看第二个问题：如果不后退到next[j],而是后退到next[j]前面，例如next[j]+2等，是否也存在满足后退限制条件的情况？ 证：假设存在一个x>next[j]使得后退到x满足后退限制条件。 所以：T1 = T4 (在图4中T1、T2、T3、T4长度相等) 又因为：S1 = S2 所以：T2 = T4 所以：T1 = T2 所以：T1为最长前后缀匹配长度 所以：x = next[j] 所以：与假设矛盾假设不成立