软考笔记（数据结构篇）———— KMP算法

KMP 算法
主串P： a b a c b c a b a b a b b c b c
模式串S：a b a c b c a

第一步：计算模式串S的前缀码
规则: 前后缀码必须一致且是最长，不能超过模式串本身。

第二步：列好表格进行匹配，如下：

比较开始：
从模式串S[0] 和主串P[0]，开始匹配，相同。则 i++，j++；直到不匹配。
第一遍匹配到：S[3] 不等于 P[3]

此时找到模式串S[3]对应的next 值为 1，主串匹配位不变，模式串移动到 S[1]（即字符串b）

此时还是不等，接着上一步的操作，即 S[0] 和 P[3] 进行比较

这里需要注意的地方是：此时 S[0] 和 P[3] 不等。而对应模式串S位置上的next值为 -1。
到了这一步说明在主串P从开始匹配位置（即0）到结束匹配位置（即3）没有匹配到与模式串一致。

换句话说：当

软考笔记（数据结构篇）———— KMP算法最先出现在Python成神之路。