史上最详细的KMP算法教程，看这一篇就够了

🧑‍💻 文章作者：Iareges
🔗 博客主页：https://blog.csdn.net/raelum
⚠️ 转载请注明出处

目录

• 一、BF算法
• 二、KMP算法
• • 2.1 字符串基础
  • 2.2 next数组
  • 2.3 KMP的实现
  • 2.4 next数组的生成
• 三、改进的KMP算法
• • 3.1 nextval数组
  • 3.2 KMP算法最终版（nextval版）
• 四、寻找所有子串的KMP算法（推荐）
• • 4.1 前缀函数
  • 4.2 利用前缀函数实现KMP算法
  • 4.3 数组的生成
  • 4.4 KMP算法最终版（前缀函数版）
• References

⚠️ 本文讨论的下标均从 开始。

字符串匹配又称模式匹配（pattern matching）。该问题可以概括为「给定字符串 和 ，在主串 中寻找子串 」。字符串 称为模式串 (pattern)。模式匹配成功是指在 中找到了 （可能存在多个），不成功是指 中不存在 。

模式匹配的算法有很多种，这里主要讨论BF算法和KMP算法。

一、BF算法

BF（Brute-Force）算法为暴力解法。设主串 ，模式串 ，分别用 遍历 和 （初始均为 ），其基本过程如下：

• 第一趟匹配：，从 开始比较。若对应的字符相同，则继续比较各自的下一个字符。如果对应的字符全部相同且 的字符比较完，说明模式匹配成功。在比较的过程中只要有一次不相同，说明第一趟匹配失败；
• 第二趟匹配：，从 开始比较。若对应的字符相同，则继续比较各自的下一个字符。如果对应的字符全部相同且 的字符比较完，说明模式匹配成功。在比较的过程中只要有一次不相同，说明第二趟匹配失败；
• 以此类推，只要有一趟匹配成功，就说明 是 的子串，返回 在 中的起始下标。如果 超界都没有匹配成功，说明 不是 的子串，返回 。

BF算法的实现如下：

int bf(const string &s, const string &t) {
    int i = 0, j = 0;
    while (i < s.size() && j < t.size()) {
        if (s[i] == t[j]) i++, j++;
        else i = i - j + 1, j = 0;
    }
    if (j == t.size()) return i - j;
    else return -1;
}

BF算法的动画演示：