之前说到，朴素的匹配，每趟比较，都要回溯主串的指针，费事。则 KMP 就是对朴素匹配的一种改进。正好复习一下。
KMP 算法其改进思想在于：
每当一趟匹配过程中出现字符比较不相等时，不需要回溯主串的 i指针，而是利用已经得到的“部分匹配”的结果将模式子串向右“滑动”尽可能远的一段距离后，继续进行比较。如果 ok，那么主串的指示指针不回溯！算法的时间复杂度只和子串有关！很好。
KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的，很自然的，需要一个函数来存储匹配失败的信息。
先理解一个概念：前后缀字符串
比如"ababa"
前缀：a，ab，aba，abab，除了最后一个字符
后缀：a，ba，aba，baba，除了第一个 字符
比如"abcd"
前缀：a，ab，abc
后缀：d，cd，bcd
图解kmp 算法对朴素匹配改进的过程；
同样如图1，发生不匹配，朴素的做法是 j 到开头1出，i 到上次开始比较的位置的下一位2处（i回溯）
但是发现一个问题，那就是在 图1的3处，不匹配的时候，前面的字符已知是匹配的，ab 是模式串里临时匹配的串，如果 i 回溯，那么等于是白白去比较，因为要把"搜索位置"移到已经比较过的位置，重比一遍。无用功，如果此时 i 不动，直接就可以减少无用的比较次数（所谓无用是说以最少的比较次数，找出完全的匹配串，尽量少做不匹配比较，通过之前的信息来计算和判断），如上图2，i 不动，j 回溯到1，匹配，ij继续走……一直都是匹配的，直到图4
那么不匹配了，临时的匹配串是 abca，如果 j 还是回到1，i 回溯到4（朴素的），我们发现1和4比较后不匹配，那么 i 继续右移，j 还是1，直到 i 到了6，才和 j=1处的 a 匹配，是不是之前的比较都是无用功？为什么不可以直接就和6比较呢？怎么解决呢？
发现一个规律：如果临时匹配串里，前后缀有重复，那么其实模式串的j，没必要每次都回到1，仔细思考是这样的。有一定规律可寻。
整个过程结束，最后结果和朴素一样，但减少了比较次数，改进了时间复杂度，让 o（t） 只和模式串t有关，因为主串s是给定的，且 i 不回溯，一直往前走！
到这里，就要思考，如何找出 j 回溯的逻辑。
换一个角度思考；
之前我们的做法是都观察 i j 的回溯！如图，现在我们移动模式串来观察。
图7不匹配， i 到2，j 到1，其实这相当于 T 右移，看图8。T 继续右移直到发生匹配，顺次比较，直到图9，红色标出，发现了不匹配，那么，按照之前的朴素做法，i 到4，j 还是1，相当于 T还是 右移一位！如下下图10。
比较之后，不匹配，T 继续友谊，直到T 1处移动到S6处，才发生匹配，之后继续顺次比较，ok！找出了匹配串。