超级直白的KMP算法理念解释

1、KMP算法要解决的问题：

字符串模式匹配：
给定两个字符串：
   S=“s1s2s3 …sn”
   T=“t1t2t3 …tn”
（官方说法）在主串S中寻找子串T的过程叫做模式匹配，T称为模式。
（直白说法）判断 T 是否为 S 的子串。

2、没有KMP算法的时候，有一种暴力算法，也可以叫笨方法。

图解暴力算法：



重复以上步骤，直到↓

每次遇到不一致就回溯S，起始位置向后移动一重新开始和P比较。

那为什么之前程序里会用这种暴力方法呢？
因为机器，最会做的就是机械式的重复工作、依次遍历内存工作啊！只需要按照内存一个一个去比较，一开始从S的第一位去找P，不一样那就从S的第二位重新开始找就好了，直到找到S中的P或者S结束。这样机器很容易理解，但是算法性能不强。

但是，你想想，有一些生活经验的人 在寻找S 中是否包含 T的时候，是以上做法吗？当然不是！接下来展示人们思考时的做法：
1、当第一次比较遇到不匹配的地方时(S[i]和P[j]不匹配)，我们就会想，那么下一次我们从哪里开始比较好呢？此时通观察，发现红框里的S与P的子串一样诶！

2、那么我就不用回溯S，而是回溯P（可以想象为移动P，但是在计算机中，P的存储位置一直是不变的，只是指针指向回到了前边的位置）

上图是 j回溯 == 下图的视觉上的P移动

s[i] = p[j]，i、j一起右移一位，直到P结束（P是S的子串）或者S结束（P不是S的子串）或者s[i] != P[j]（重复以上操作）

3、观察上边最后一幅图，S[i]!=P[j]。显然只要右移P的绿色部分，两者就会不匹配，所以下一步直接把j回溯到P的起始位置。i不动。

上图是 j回溯 == 下图的视觉上的P移动

从第一个就不相等，那么j也没有刻意回溯的地方了，所以i向后移动，j指向不变也就相当于右移一下。

以上是我粗略的展示了一下人脑的思考过程。显然比暴力算法节省了好多时间。那么为什么这种方法快呢？因为我们可以 预览全局。也就是我们能看到下图中S绿色部分的后缀AC和p绿色部分的前缀AC相同，而且此时S绿色部分和P的绿色部分是完全匹配的，也就是：
P的前缀AC = S的后缀AC= 自己的后缀AC（蓝色框）

因此，就引出了在程序中，我们要借助串P的 各个子串的最大公共前后缀 来让程序拥有和人类一样 预览全局的能力，省掉重复而无用的比较步骤

3、串P的各个子串的最大公共前后缀

4、后记

理解了kmp算法的理念，但是kmp算法的代码实现很精妙且有点难以理解，下次再解释吧！