字符串 | 字符串匹配之 KMP 算法及其实现（基于Python）

目录

• • 1 为何选择 KMP 算法？

    • 2 next 数组的定义是什么？

    • • 2.1 字符串的前后缀概念解析
      • 2.2 next 数组的计算方法

    • 3 KMP 算法的具体实现

    • 4 完整代码示例

---

😈前言：本文篇幅较长，但我认为已经将相关内容解释得较为清晰

1 为什么使用 KMP？

【首先需要说明的是，在进行字符串匹配操作时，所涉及的两个字符串分别被定义为“主串”与“模式串”。

答：在采用朴素字符串匹配方法时，一旦发现主串中的字符 s[i] 与模式串中的字符 p[j] 不一致，就需要将主串和模式串都回退至起始位置，并使模式串从主串的下一个字符位置重新开始匹配。KMP 算法的提出正是为了解决这一问题，该算法的优势在于无需对主串进行回溯操作，仅需对模式串进行局部回退，从而有效减少了大量无效且无法成功的匹配步骤。

上述内容仅为简要说明其原理，若存在理解困难则属正常现象。

2 什么是 next 数组？

next 数组作为 KMP 算法中的一项关键辅助结构，其核心在于理解其定义及生成方式即可。

• 定义：该数组所存储的数值，表示特定字符串中前缀部分与后缀部分相匹配的最长长度。

2.1 什么是字符串的前后缀？

前缀与后缀的概