KMP算法的资料网上已经一大把了，主要用来解决某个文本片段是否包含另一个子串问题。这里假设文本片段的长度n大于子串长度m，如：

文本串为ABCDABGHIJK

子串为   ABCDABE

在传统的暴力解法中当子串的E与主串的G不匹配时，将文本串从B开始、子串从头开始重新匹配，这样的时间复杂度为(n-m+1)*m,很显然效率是比较低的。

KMP算法的思想是当子串的E不匹配时，文本串保持在G位置，子串从C位置开始匹，关键就是要知道：

1、为什么是C这个位置？

2、如何求C这个位置？

先说第一个问题：直观的看是因为C前面的AB与G前面的AB正好能够匹中。但实际上就像采用暴力法解决时，本质上是在查找子串ABCDABE与剩余文本串BCDABGHIJK的第一个能找到子串最长前缀AB的位置，由于KMP算法不想让未匹中字符G的位置进行回溯即已经固定，所以就等价于查找子串ABCDABE与剩余文本串BCDAB的最长公共前缀问题。由于最长公共前缀是AB所以子串从C位置开始匹。

再说第二个问题：查找子串ABCDABE与剩余文本串BCDAB的最长公共前缀问题等价于计算子串ABCDA与剩余文本串BCDAB的最长公共前缀问题（因为最长公共前缀的长度一定是<=剩余文本串BCDAB的长度），因此也就等价于计算字符串ABCDAB的最长公共前后缀长度也就是计算集合（ABCDA、ABCD、ABC、AB、A）与集合（BCDAB、CDAB、DAB、AB、B）的交集中字符长度最长的字符即AB。

求解的方法比较简单将ABCDA与BCDAB比较、ABCD与CDAB比较、ABC与DAB比较、AB与AB比较、A与B比较即可。

实际上子串的每个字符都要求出当不匹配时指针应该停留的位置，这个在匹配前需要进行预处理，预处理的方法就是求解第二个问题的方法。