KMP算法我在网上搜了很多说明，但论简洁易懂还属
阮一峰
的那篇文章，强烈推荐大家看看
个人觉得唯一不足之处在于《部分匹配值》的计算方法描述有些不清楚，在此按自己的理解更详细的详解一下
取阮总文章中的例子进行说明，搜索词及《部分匹配值》如下图如示：
一开始我一直以为单个字符进行计算，后来经过查询资料发现我错了，每个字符下面记录的部分匹配值不是这单个字符的值，而是从开头字符到此字符这个字符串的值，这样说可能有点抽象，下面以上图为例详细讲解一下
为了方便说明这里把搜索词记为：P={ABCDABD}
-
1，P[0]表示“A”，其完全前后缀都是空，所以其部分匹配值为0
-
2，P[1]表示“AB”，其完全前缀为{空，A}，完全后缀为{B，空}，前后缀中只有空相同，所以AB(即P[1])的匹配值为0
-
3，P[2]表示“ABC”，
其完全前缀为{空，A，AB}，完全后缀为{BC，B，空}，前后缀中只有空相同，所以ABC(即P[2])的匹配值为0
-
4，P[3]表示“ABCD”
，
其完全前缀为{空，A，AB，ABC}，完全后缀为{BCD，CD，D，空}，前后缀中只有空相同，所以ABCD(即P[3])的匹配值为0
-
5，P[4]表示“ABCDA”，
其完全前缀为{空，
A
，AB，ABC，ABCD}，完全后缀为{BCDA，CDA，DA，
A
，空}，前后缀中都有{A}长度为1，所以ABCDA(即P[4])的匹配值为1
-
6，P[5]表示“ABCDAB”
其完全前缀为{空，A，
AB
，ABC，ABCD，ABCDA}，完全后缀为{BCDAB，CDAB，DAB，
AB
，B，空}，前后缀中都有{AB}长度为2，所以ABCDAB(即P[5])的匹配值为2
-
7，P[6]表示
“ABCDABD”
其完全前缀为{空，A，AB，ABC，ABCD，ABCDA，ABCDAB}，完全后缀为{BCDABD，CDABD，DABD，ABD，BD，D，空}，前后缀中只有空相同，所以ABCDABD(即P[6])的匹配值为0
说明：
-
P[i]表示能匹配的字符串，部分匹配值计算的是能匹配的字符串对应该的值，例如上面的P[5]表示的是如果匹配了字符串“ABCDAB”，则
这个字符串对应的部分匹配值为2，而不是第二个字符B的部分匹配值
-
为了方便操作，
字符串的部分匹配值都对应到字符串的最后一个字符
，这样即方便记录也方便查询
另外，
“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度，这个已经在阮总的文件中解释，
这里再强调一点，其前后缀都是表示完全前后缀，即不包含自身的前缀或者后缀
。