1. 字符串匹配问题
假如我们有一个模式字符串ABCDABD和一个目标字符串BBC ABCDAB ABCDABCDABDE，
我们怎样找到模式串在目标串中的匹配位置呢？
最容易想到的办法是逐个比对：源码
2. KMP算法背景
KMP算法是一种改进的字符串匹配算法，
由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为KMP算法。
KMP算法的关键是利用匹配失败后的信息，
尽量减少模式串与目标串的重复匹配次数以达到快速匹配的目的。
具体实现是利用一个事先计算好的next数组，
其中包含了模式串的前缀与后缀特征。
3. 往后跳多远
我们观察一下，看看逐个比对会包含哪些重复计算，然后想办法消除它。
考虑某个中间步骤，
BBC ABCDAB ABCDABCDABDE
ABCDABD
模式串ABCDABD的子串ABCDAB都比对成功了，可是，在D处失败了。
于是下一步，我们会向后移动一个字符，继续比对，
BBC ABCDAB ABCDABCDABDE
ABCDABD
可是，我们可以移动的更远一些吗？
能不能把目标串中的ABCDAB全都跳过？
BBC ABCDAB ABCDABCDABDE
ABCDABD
好像不行，跳的太远了，我们得从这里开始，
BBC ABCDAB ABCDABCDABDE
ABCDABD
因为ABCDAB前缀和后缀包含重叠的部分。
我们称
AB为ABCDAB的前缀和后缀的最长公共序列。
跳多远=
ABCDAB长度 - 前缀和后缀的最长公共序列长度
4. next数组
前缀和后缀的最长公共序列，只和模式串有关，是模式串本身的特征。
所以，我们就可以事先算好模式串前n个字符的前缀和后缀的最长公共序列的长度，
把它们存起来，称为next数组。
对于模式串agctagcagctagct来说，
它的next数组为[0,0,0,0,1,2,3,1,2,3,4,5,6,7,4]，
即，模式串的前i+1个字符的前缀和后缀的最长公共序列的长度为next[i]。
例如：agctagcagctagct的前6个字符agctag的前缀和后缀的最长公共序列的长度为next[5]=2。
怎样计算这个数组呢？
我们可以利用next[0]~next[i]来计算next[i+1]。
假设pattern='agctagcagctagct'
a：next[0]=0，
ag：pattern[1]=g，pattern[0]=a，不相等，所以next[1]=0，
agc：pattern[2]=c，pattern[0]=a，不相等，所以next[2]=0，
agct：pattern[3]=t，pattern[0]=a，不相等，所以next[3]=0，
agcta：pattern[4]=a，pattern[0]=a，相等，所以next[4]=1，
agctag：pattern[5]=g，pattern[1]=g，相等，所以next[5]=2，
agctagc：pattern[6]=c，pattern[2]=c，相等，所以next[6]=3，
……
agctagcagctagc：pattern[13]=c，pattern[6]=c，相等，所以next[13]=7
5. 次长公共序列
难点来了。
agctagcagctagct：pattern[14]=t，pattern[7]=a，不相等。
怎么办？于是next[14]=0吗？
很显然不行，因为agct是前缀和后缀的最长共同序列，next[14]=4。
寻找agct基于以下考虑，
如图，橙色的A表示已经确定的最长公共序列，绿色的T将要与开头的A后面的元素进行比较。
如果比对失败，我们需要寻找次长公共序列B，然后T再与开头的B后面元素进行比对。
我们看到，三幅图中，橙色块都是相等的，
如果存在次长公共序列，第二幅图表明，橙色块必然同时以B开头且以B结尾。
即，如第三幅图所示，
这表明，T位置的次长公共序列长度，就是橙色块的最长公共序列长度。
因此，计算agctagcagctagc的次长公共序列，就要计算B=agctagc的最长公共序列，
而这个已经计算过了，next[6]=3，得到agc。
然后与agc后面的元素t进行比对，相等，next[14]=4。
参考：
Github：kmp源码
视频：求kmp的next数组
从头到尾彻底理解KMP（2014年8月22日版）
字符串匹配的KMP算法- 阮一峰的网络日志
网友评论