KMP算法详解
这篇文章用于总结自己对KMP算法的一些理解，如有错误，请不吝指出。
KMP算法用于字符串匹配加快进程。
例如对于以下问题：
在字符串ABAACCABD中查找是否含有ABD这个串？
对于这个问题，很快就可以想到直接暴力搜索，多个循环依次匹配字符来达到目的，这种方法虽然简单易懂，但是效率很低。应用KMP算法可以有效地提高字符串匹配的效率。简单来说KMP算法是利用了已经匹配过的字符的信息来加快匹配的进程。例如
ABAACCABD
| | |
ABD
当检索到第三位时，A与D并不匹配，暴力算法会直接将字串从第二格开始重新检索，但是在KMP算法中会试图利用第一位的A与第二位的B互相已经匹配的信息来跳过一些不必要的步骤，已到达加速的目的。我个人认为实际上是利用了字符串中的回文（好像也不是），在详细解释KMP算法是如何利用这些信息加速之前，首先我们需要了解字符串前缀和后缀的概念。
对于任何一个字符串，我们可以提取出它的前缀和后缀，例如对于ABABC这个字符串
ABABC
前缀： ABAB，ABA,AB, A
后缀： BABC, ABC, BC, C
通过这个例子，相信不难看出前缀和后缀的规律，实际上类似于包含第一个/最后一个字符的字串。KMP算法实际上就是对最长公共前后缀的一个利用。公共前后缀就是指前缀和后缀中相等的一部分，例如：
ABAB
前缀: ABA,AB,A
后缀 BAB,AB,B
那么ABAB的最长公共前后缀就是AB，KMP算法的核心之一就是如何找到最长公共前后缀，这里先按下不讲，先解释如何利用最长公共前后缀来加快匹配的进程。
ABABAAAAACABABC
| | | | ？
ABABC
对于这个两个字符串，公共前后缀已经标注成了红色，首先我们还是依次匹配，前面的ABAB都是完全相等的，知道第五位的A 与C不匹配，暴力算法会将ABABC向右移一位重新循环，从第一位开始继续匹配，KMP算法则会直接右移两位从第五位开始。（这里的第几位指的是主串中的位置）
ABABAAAAACABABC
|
ABABC
暴力算法
ABABAAAAACABABC
|
ABABC
KMP算法
原因就在于在KMP算法中，我们已经得出了字串的公共前后缀AB，也就是在字串中一定存在一个前面AB = 后面的AB。在和主串匹配的过程中，因为ABABC中的ABAB部分是和主串中的前四位完全相等的，那么也就意味着主串之中也一定有一个前面AB=后面的AB，而实际上第一次匹配的过程中正式主串的前缀AB=字串的前缀AB，主串的后缀AB=字串的后缀AB。如下图所示：
ABABAAAAACABABC
ABABC
KMP算法的做法就是，直接用字串的前缀AB去对主串的后缀AB
ABABAAAAACABABC
ABABC
因为字串的前缀AB=字串的后缀AB，字串的前缀AB又等于主串的前缀AB，那么显而易见字串的前缀AB也等于主串的后缀AB，而且由于我们已知它们相等，就不用从主串的第三位开始匹配，直接跳过后缀AB到主串的第五位A进行比较即可。我刚开始了解的其中一个疑惑时，这样跳不会漏掉中间的字符导致结果不对吗？这里我自己的想法是，实际上得出公共前后缀的过程已经排查了漏掉的情况，因为目的是去找完全相同的字符串，那么必须要保证所有的字符都相同，得到了最大的公共前后缀，也就意味着主串后面存在某一段字符串和字串中的前缀完全相同，当遇到不匹配的字符之后，只需要直接将字串的前缀挪到主串的后缀即可。（这段比较乱，随意看看即可）
接下来再看一个类似的例子，还是ABABC
ABACAAAAACABABC
| | | ?
BBABC
在这个例子中，第四位就已经不匹配了，我们应该根据ABA这个字符串的公共前后缀来计算，也就是A，那么只需要将ABABC挪到如下位置即可：
ABACAAAAACABABC
| ?
ABABC
那么对于我们想要查找的ABABC这个字符串，我们应该分别计算出它每一个字串的最长公共前后缀的长度即，
A 0
AB 0
ABA 1
ABAB 2
ABABC 0
我们把得到的这组数字成为最长长度表：
ABABC
0 01 20
根据这组数字，将在最前方插入-1就得到了Nxet数组用来指引字串的下一位置即
ABACAAAAACABABC
| | | ?
ABABC
-1001 2
当第四位的C与B不匹配时，Next数组的值为1，我们只需要将字串中的第一位（从第零位开始计算）移动C的位置即可，也就是
ABACAAAAACABABC
| ?
ABABC
-100 1 2
然后C与B还是不匹配，根据Next数组，将第零位移动到这个位置。当Next数组等于-1时，直接将字串往后推一位。
ABACAAAAACABABC
?
ABABC
-100 1 2
以上就是KMP算法如何利用Next数组加速匹配过程，然后继续介绍如何在字串中求得Next数组。
对于任意一个我们想要搜寻的字符串，首先我们需要求得该字符串每个字串的最长公共前后缀长度的数组，并根据这个数组找出Next数组。任然举ABABC这个例子
ABABC
当我们求A的最长公共前后缀长度时，显而易见，应该是0，因为他没有任何字串，由此可以类推，所有字符串的长度数组L[0] = 0(用L表示长度数组，用N表示Next数组).
关键是如何求得任意一个L[K]的值，首先L[K]的值最多等于L[K-1]的值+1，因为在已知L[K-1]的最长公共前后缀长度，新加一个字符，那么最多就是直接相等，这种情况如下下图
ABAB？
已知ABAB的最长公共前后缀长度为2，即AB，当我们求ABAB?的公共前后缀时，只需要首先考虑前缀AB加上后面一位字符A是否等于后缀AB+后面一位字符？即ABA == AB？吗，如果此时？的位置是A，那么我们很快就可以得出ABABA的最长公共前后缀为3。以此类推当我们计算L[K]时首先比较L[K-1]的前缀+后一位字符是否等于L[K-1]的后缀+新的字符，如果相等L[K]=L[K-1]+1.这是最简单的一种情况。第二种情况就是不相等
ABAB? 如果此时?等于B，那么就不满足上述情况了，为了便于理解，我举一个更长的字符串当例子。
ABABABABB
对于这个字符串，不难看出他的前八位最长公共前后缀为ABAB，四位，现在我们要求第九位的最长公共前后缀长度。
ABABABAB？
为了便于理解，将前八位的前缀和后缀分别标注出来，此时当？= B那么不满足上述说的第一种情况，但是我们可以发现实际上第一种方法可以总结为 前缀+后一位字符是否 == 后缀+新字符，如果相等则长度+1就是结果。
ABABABAB？
即使不满足上述情况，因为前缀字符串等于后缀字符串，也就意味着前缀的前缀字符串，等于后缀的后缀字符串。如上图所示 红绿色AB表示前缀ABAB的前后缀，蓝黄色AB为后缀ABAB的前后缀，此时我们只需要再次验证红色前缀AB+后一位字符是否等于黄色前缀AB+新字符如果相等，那么第九位公共前后缀长度就应该等于ABAB的最长公共前后缀长度+1，如果不等，那么重复上述过程，直到前面的字符串公共前缀长度为0，那么所求的公共前后缀长度也等于0.回到举得第一个例子
ABAB？
如果？不等于A，那么则继续看前缀AB的公共前后缀，显而易见应该是0，那么ABAB？的公共前后缀长度就等于0. 最后在L数组的最前方插入-1就等于Next数组了。
以上是个人对于KMP算法一点总结，语言混乱，如有错误，请不吝指出。
