文档介绍：KMP算法在子串匹配失效的时候,下一步并不是重新从子串的头部开始匹配,而是根据一下next函数计算出下一步应该从子串的什么部位开始匹配。举例如下:
红色为失效位置, '^'表示的当前是指针位置,'~'表示此次匹配A串开始的位置。
若是普通的匹配算法,当失效时,C串指针要回溯到头部,A串指针也要回溯到'~'的下一位。也就是下一步应该是从A的第二字符(. 'b')和C的开头(. 'a')开始匹配。如此循环
直到找到A串中的某一个位置可以匹配C串。
然而从上面的匹配过程中,可以发现A和B的蓝色部分是第一步中已经确认匹配过的,上面四步的匹配其实可以看作是蓝色部分的前半段与后半段在进行比较,而且前三步在蓝色部分就已经匹配失效了,所以这些比较是无谓的,因为它与父串A无关的,是属于子串C本身的信息。只有第四步才涉及了与父串A中的字符('c')的比较。
KMP算法正是利用这一点,它事先利用子串本身的信息就计算出当某一次匹配失效时,下一次应该继续匹配的位置。也就是当C串在最后一个'b'匹配失效时, 它省略了前三步(1,2,3)无谓的匹配,下一步比较将在'd'与'c'之间进行。这样父串A无需回溯,C串用一个next函数决定它将回溯的位置。所以 next函数至关重要,也是这个算法的关键。
从上面的分析可以知道next函数是子串C本身的性质决定的,假设子串P = P0P1...Pn-1
next(j)=k(k>=0): 当P的第 j+1个字符匹配失败时, 在父串指针不回溯的情况下,下一步将与Pk+1比较。
当next(j)=k (k>=0)时,子串指针回溯到Pk+1的位置,父串指针不变;
当next(j)=-1时,子串指针回溯到头,父串指针前进一步;
在设计计算next值的程序的时候,我们没有必要每一步都去计算maximum(k),可以用递归方式来做
举个例子
假设子串为P:"abacaba
b", 且我们将要求的是'b'的next值, . next[7]
假设next[0~6]均为已知: next[0]=-1, next[1]=-1 , next[2]=0 , next[3]=-1 , next[4]=0 , next[5]=1 ,next[6]=2
  "abacabab"
next[6]=2可以说明P[0~2](蓝)与P[4~6](红)是一样的
要求next[7]的值,我们可以找前6位("abacaba")中最长的前半段与后半段相等的子串,然后比较前半段子串的下一位是否和P[7]相等。在这个例子中, P[0~next[6]](. P[0~2])就是这样的子串,接下来我们比较 c 和 b也就是P[next[6]+1]('c')和P[7]('b').
若相等则 next[7] = next[6]+1
若不等, 我们进一步找更短的前半段与后半段相等的子串,因为aba和aba是一样的, 要找'abacaba'中比'abc'短的这样的子串,相当于找'aba' 中的next[2][next[6]]的值。然后再比较P[next[next[6]]+1]和P[7]是否等,若不等则继续找更短的这样子串
在上的例子中 P[next[6]+1]=P[3]('c') ,与P[7]('b')不相等, 但是