kmp算法是一种效率非常高的字符串匹配算法，是由Knuth，Morris，Pratt共同提出的模式匹配算法，所以简称KMP算法
在一个字符串中查找另一个字符串时，会遇到如下图的情况
我们通常的做法是从第一个串A的下一位B再逐位比较，但这样的做法非常低效。
仔细思考一下发现，第一个串已经匹配的部分就是第二个串的前缀。如果我们对第二个串进行一些预处理，或许就不用再去逐位比较了。
KMP算法就是预处理出要查找串每个前缀的最大相同前后缀的长度，通俗一点就是两个相同的串在不重合情况下最大的重叠长度
如上图中ABCDAB前缀的最大相同前后缀就是AB，长度为2
这样我们在D匹配不成功时，就可以直接将查找串贴到匹配成功部分的后缀与查找串前缀的最大相同部分上继续匹配，如图
原文：http://www.cnblogs.com/bennettz/p/7648863.html