比较通俗的介绍|比较通俗的介绍 KMP 算法
主串：acabaabaabcacaabcKMP 算法就是在主串中去寻找模式串的一个时间复杂度为 O(n + m) 的算法，其中 n，m 分别为主串、模式串的长度。
模式串：abaabcac
KMP 算法的核心思想就是利用已经得到的“部分匹配”的结果，将模式串的起始位置相对于主串直接向右滑动一段距离。那么问题的关键就是这段距离的长度怎么确定？
KMP 算法中有一个 PMT(Partial Match Table) 的概念。至于每次滑动多远的距离就根据 PMT 来确定了。我们先给出上面给出的模式串的 PMT。
| a | b | a | a | b | c | a | c |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 2 | 0 | 1 | 0 |
a每个子串都有自己的前缀和后缀，前缀和后缀相同的情况下的最大的长度就是我们要的 PMT 表的值。
ab
aba
abaa
abaab
abaabc
abaabca
abaabcac
【比较通俗的介绍|比较通俗的介绍 KMP 算法】ab：没有相同的前缀和后缀，所以该位置的值为 0得到这个 PMT 表以后，每次移动的长度：
aba：前缀 a 和 后缀 a，再没有更长的了。该位置的值为 1
abaab：前缀 ab 和后缀 ab 相同，没有更长的了。该位置的值就为 2
补充：起始位置默认为 0
移动位数 = 已匹配的字符数 - 最后一个匹配的字符在PMT表中对应的值。还是举例说明：
| a | c | a | b | a | a | b | a | a | b | c | a | c | a | a | b | c |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| a | b | a | a | b | c |
| a | c | a | b | a | a | b | a | a | b | c | a | c | a | a | b | c |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| a | b | a | a | b | c | a | c |
字符串的 KMP 算法
推荐阅读
- 热闹中的孤独
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- 放屁有这三个特征的，请注意啦！这说明你的身体毒素太多
- 一个人的旅行，三亚
- 布丽吉特，人生绝对的赢家
- 慢慢的美丽
- 尽力
- 一个小故事，我的思考。
- 家乡的那条小河
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量