一、KMP算法
1.KMP算法简介
KMP算法是(D.E.Knuth、J.H.Morris和V.R.Pratt)的研究成果，大大的避免重复遍历的情况，全称叫做克努特-莫里斯-普拉特算法，简称KMP算法。
回顾BF算法，为什么效率低下：
比如，在第五个位置，j和i不匹配时，i就会回溯到第二个位置与j的第一个位置从头开始比较，回溯就是坚持条条大道通罗马的决心，然后遇到挫折就回到跌倒的地方重新爬起来，继续往前，这种思想是好的，但是效率是低下的！
二、KMP算法思路启发1
(1)思路启发一
我们观察上面两个字符串S、T：
其中：i1 == j1，i2 == j2，i3 == j3，i4 == j4
j1 != j2，j1 != j3，j1 != j4；j2 != j3，j2 != j4；j3 != j4
由此可以得出，i1 != j2，i1 != j3，i1 != j4；i2 != j3，i2 != j4；i3 !=j4
所以，我们不需要回溯，再从i2与j1进行匹配，而只需要从i5开始于j1进行匹配！
(2)思路启发二
我们观察上面两个字符串S、T：
其中：i1 == j1，i2 == j2，i1 == i2 == i3
j1 == j2，j2 != j3
所以，我们就需要将j1匹配到i2，然后将j2与i3进行匹配。
(3)思路启发三
我们观察上面两个字符串S、T：
其中：i1 == j1，i2 == j2，i3 == j3，i1 == i2 == i4 == i5
j1 == j2，j1 != j3，j2 != j3
虽然我们可以看到i6与j6不匹配，但是我们却不知道从i6，j3开始匹配，之后是否能够匹配，所以我们需要从这里开始。
(4)思路启发四
通过思路启发三，我们很轻易的可以得到上面的思路启发四，当前面的字符都是一样的情况下，突然出现一个不相同的，我们可以把字符串T往回移动一步，然后与字符串S的最后一个字符匹配，看是否能够匹配成功。
本文为原创文章，如果对你有一点点的帮助，别忘了点赞哦！比心！如需转载，请注明出处，谢谢！
转播
