KMP算法

最长公共前后缀

在一个文本串中查找一个模式串P出现位置，
首先需要计算模式串的next数组，该数组保存模式串中前后最长公共子序列的长度。这样每次重新匹配时可以通过next数组找到前面匹配过的位置，节省时间。

对于str=“ABCABD”
从索引为0开始的子串"A"而言，前缀：包含第一个字符，不包含最后一个字符的子串们，不存在，
后缀：包含最后一个字符，不包含第一个字符的子串们，不存在，
该子串的最长公共前后缀为0
“AB”，前缀：B；后缀：A，最长公共前后缀为0
“ABC”，前缀：A, AB；后缀：BC, C；最长公共前后缀为0
“ABCA”，前缀：A, AB, ABC；后缀：BCA, CA, A；最长公共前后缀为1（因为长度为1）
“ABCAB”，前缀：A, AB, ABC, ABCA, ABCAB；后缀：BCAB, CAB, AB, B；最长公共前后缀为2（因为长度为2）
“ABCABD”，前缀：A, AB, ABC, ABCA, ABCAD；后缀：BCABD, CABD, ABD, BD, D；最长公共前后缀为0
next数组为[0,0,0,1,2,0]

算法步骤

1. 待匹配的字符串为matchStr，模式字符串为patternStr。求出模式字符串patternStr的部分匹配表next，设置两个指针i,j，分别指向matchStr和patternStr，初始化为0，判断matchStr[i]和patternStr[j]是否相等，相等则i++, j++向后继续匹配。
2. 如果不相等，则i不变，调整j=next[j-1]：因为这个时候（matchStr[i-j, i-1]和patternStr[0, j-1]是相等的），某个字符串的最长公共前后缀的长度就是表示从开头开始的某个子串和从中间到结尾的某个子串是一样的，最长的这个长度就是最长公共前后缀的长度。也就是如果matchStr[i-j, i-1]==patternStr[0, j-1]，但是下一个字符不相等，但是我们又不希望从matchStr[i-j+1]开始逐字符比较，我们希望存在一个索引位置，使得matchStr[i-j, i-1]中从该索引往后的直到 i-1的子串和patternStr[0, j-1]的前面的部分子串是相等的，这个长度也就是patternStr[0, j-1]最长公共前后缀子串的长度，因此考虑将模式串待匹配位置进行更新，即更新到最长公共前后缀子串的下一个位置，也就是next[j-1]（因为next[j-1]是长度，而位置从0开始，下一个位置正好是next[j-1]-1+1），然后判断是否相等，递归，不相等再返回步骤。
3. 判断i和j是否超出各自的最大索引值，如果j超出了模式串的最大索引值，说明匹配成功，返回位置i-j，如果i超出最大位置则判断j是否超出，如果j没有超出，则匹配失败。