串 - KMP算法

发布时间 2023-11-03 12:12:26作者: Mira_2019

数据结构算法中重中之重。肯定考。

 

 

针对该算法,ShoelessCai 打算用几个问题来梳理清楚:

1. 算法返回什么? 返回的是 主串的位置 i

2. 算法输入什么? 主串、模式串(较短的)、Next数组(记录模式串位置)

3. 基本思想:

如果匹配失败的时候,从失败位置,往前搜索,有多少个字符 SLOTS是一致的?一致的部分保持一致,再移动模式串。这样移动起来是不是快很多呀?不然就是一个一个移动。

4. Next[] 长度和模式串一致。构造方法,匹配 SLOT 之前最长子串,比较前缀、后缀重叠的 SLOTS 个数,姑且称为 N。Next[] 中的元素为 N+1

5. 应该有其他办法算出 Next[] , 待更新。