学习笔记：KMP

tsqtsqtsq0309 · 2023-09-26 20:01:00 · 算法·理论

KMP

引入

KMP 算法（全称 Knuth-Morris-Pratt 字符串查找算法，由三位发明者的姓氏命名）是可以在文本串中快速查找模式串的一种算法。

实现

要想知道 KMP 算法是如何减少字符串查找的时间复杂度的，我们不如来看暴力匹配方法是如何浪费时间的。

所谓暴力匹配，就是逐字符逐字符地进行匹配，如果当前字符匹配成功，就匹配下一个字符，如果失配，i回溯，j置为0。代码如下：

// 暴力匹配
int i = 0, j = 0;
while(i < s.length()){
    if(s[i] == p[j])i++,j++;
    else i = i - j + 1,j = 0;
    if(j == p.length()){ // 匹配成功
        // 对s[i - j .. i - 1]进行一些操作
        cout << i - j << endl;
        i = i - j + 1;j = 0;
    }
}

举例来说，假如s="abababcabaa", 我们暴力匹配，过程会是怎样？

从头开始匹配，第一个字符是 a，匹配成功。

第 2~4 个字符也匹配成功，继续。

下一位，匹配失败，回溯。

匹配失败，继续尝试。

下一位，匹配成功。

就这样一直匹配到结尾。

设两个字符串的长度分别为 n 和 m ，则暴力匹配的最坏时间复杂度是 O(nm)。究其原因，在于 i 进行回溯浪费了时间。能不能让 i 不走回头路呢？然而，如果 i 不回溯，同时又把 j 置为 0，很可能会出现缺漏，如下图。

这样配下去会漏掉一个匹配，从而得到错解。

于是为了让 j 被赋为一个合适的值，我们引入了 PMT（Partial Match Table，部分匹配表）。