转载https://www.cnblogs.com/dragondragon/p/11327845.html
自我总结：
KMP算法的本质并不复杂，其思想是：将pattern与同样字符长度的text滑动窗口的字符串从左至右比较是否匹配，如果text窗口字符串与pattern字符串在匹配过程中存在部分匹配，则可以利用这个部分匹配的字符串的性质（这个部分匹配的字符串 显然也是pattern字符串的子字符串），利用这个子字符串的信息（在预处理阶段做好查找表），决定比对窗口下次往右滑动的距离（不用像暴力比对方式每次只能往右移动一个字符的距离）。
所以利用的是pattern字符串的 从左至右的子字符串的 性质。
这个子字符串对应比较匹配过程中的部分匹配的字符串，然后寻找这个子字符串的前缀和后缀中的公共元素的最大值。
例子如下：
image.png
如果给定文本串S=“BBC ABCDAB ABCDABCDABDE”，和模式串P=“ABCDABD”，现在要拿模式串去跟文本串匹配。
image
（1）. 因为模式串中的字符A跟文本串中的字符B、B、C、空格一开始就不匹配，所以
直接将模式串不断的右移一位即可，直到模式串中的字符A跟文本串的第5个字符A匹配成功；
image
（2）. 继续往后匹配（continue to match!），当模式串（P="ABCDABD"）最后一个字符D跟文本串匹配时失配，显而易见，模式串需要向右移动。
但向右移动多少位呢？
因为
（2）.1：此时已经匹配的字符数为6个（ABCDAB），
（2）.2：然后根据《最大长度表》可得失配字符D的上一位字符B对应的（ 还并不是next数组哦！是到B这儿的相同前缀后缀的最大长度！）长度值为2，
（2）.3：需要向右移动6 - 2 = 4 位。
image
（3）. 模式串向右移动4位后，发现C处再度失配，
（3）.1：此时已经匹配了2个字符（AB），
（3）.2：上一位字符B对应的最大长度值为0，
（3）.3：向右移动：2-0=2位.
image
（4） A与空格失配，向右移动1 位。
image
（5）继续比较，发现D与C 失配，
（5）.1：已匹配的字符数6
（5）.2：上一位字符B对应的最大长度2，
（5）.3：故向右移动的位数为：已匹配的字符数6减去上一位字符B对应的最大长度2，即向右移动6 - 2 = 4 位。
image
（6）： 经历第5步后，发现匹配成功，过程结束。
通过上述匹配过程可以看出，问题的关键就是寻找模式串中最大长度的相同前缀和后缀。
网友评论