KMP算法详解

常规
1

KMP算法

Part 1# 引子

KMP是一种解决子串匹配问题的算法，子串匹配问题可以抽象化成如下形式

\text{给定一个文本} \mathbf{t} \text{和一个字符串} \mathbf{s} \text{，我们尝试找到并展示} \mathbf{s} \text{在} \mathbf{t} \text{中的所有出现}

如何朴素地解决？

逐个并尝试可能存在的位置:先尝试第一个可能匹配的位置，移动字符串 \mathbf{s} 的指针 \mathbf{i} 尝试从 \mathbf{t} 第一个开始尝试，内层遍历 \mathbf{t} 的指针 \mathbf{j} ；匹配失败就将回退指针 \mathbf{j} ，并右移指针$\mathbf{i}$ ；一直到匹配成功。

#include<iostream>
#include<string>
using namespace std;
string t="ababcabcacbab";
string s="abcac";
void naiveSearch()
{
    int n=t.size(),m=s.size();
    for(int i=0;i<=n-m;i++)
    {
        int j=0;
        while(j<m and t[i+j]==s[j]) j++;
        if(j==m) cout<<"Found at index "<<i<<endl;
    }
}
int main()
{
    naiveSearch();
    return 0;
}

很容易发现，这是一个 O(nm) 的算法。

如何优化？

很容易发现，之前的算法为什么慢，主要因为有太多的重复操作了（主要是对指针 \mathbf{j} 的回退次数过多），减少回退次数成为关键。

所以解决问题的方法变成了如何预处理以节省冗余。

让我们回顾一下之前的朴素算法，发现可以不回退指针 \mathbf{j} ，使用一个数组（前缀数组）记录。

通过预处理模式串，构建部分匹配表（又称为“前缀函数”或“ \mathbf{next} 数组”），有效减少重复匹配操作，从而将子串匹配的时间复杂度优化到 O(n+m)。

如果你不明白KMP如何利用前缀数组是工作的，在下一章里我们将会提到。

Part 2# KMP 是如何工作的？

在前一章里，我们提到了利用预处理来减少重复匹配，而关键的预处理结构就是 前缀数组（prefix function），通常也称作：

  • next 数组
  • 失配函数（failure function）
  • 部分匹配表（partial match table）

这一节我们将解释：

  1. 什么是前缀数组
  2. 如何构建前缀数组
  3. 为什么它能帮助我们减少回退，提高匹配效率
  4. KMP 的完整匹配过程
  5. KMP 的 C++ 实现

什么是前缀数组？

给定模式串 s，前缀数组 pi[i] 定义为：

s[0…i] 的最长相等前后缀的长度

例如字符串：

s = "abcac"

它的前缀数组是：

索引 字符 pi[i]
0 a 0
1 b 0
2 c 0
3 a 1 （前后缀 “a”）
4 c 0 （没有相等的前后缀）

这张表告诉我们：
当匹配到位置 i 且失配时，下一次应该从 pi[i−1] 继续尝试。

也就是说：
如果 "abcac" 匹配到第 3 个字符 "a" 之后失配，我们不需要回到开头，而是跳到前缀 "a" 的后面继续匹配。

如何构建前缀数组？

下面是构建 KMP 前缀数组的模板代码：

vector<int> prefix_function(string s)
{
    int m = s.size();
    vector<int> pi(m, 0);
    for(int i = 1; i < m; i++)
    {
        int j = pi[i - 1];
        while(j > 0 && s[i] != s[j]) j = pi[j - 1];
        if(s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

算法核心：

  • j 表示当前匹配的最长前后缀长度
  • 如果 s[i] 与 s[j] 匹配，则 j++
  • 如果失配，就利用 pi[j - 1] 回退，而不是把 j 变成 0
  • 时间复杂度是 O(m) ，因为 j 只会增加或减少，不会反复震荡

前缀数组构建的高效，是 KMP 从 O(nm) 优化到 O(n+m) 的关键。

利用前缀数组为什么能减少重复比较？

来看朴素算法中最浪费的地方：
当匹配到一半失配时，我们把模式串指针 j 退回到 0。

例如：

t = ababcabcacbab
s = abcac

朴素匹配遇到 "ababc" 时会反复重新尝试：

ababc
  abcac   ← j 回到 0，从头来

而 KMP 利用前缀数组：

ababc
  abcac
    ↑ j 不变成 0，而是跳到 pi[j - 1]

也就是：

j = pi[3] = 1

跳过无意义的比较。

这样整个指针 j 总共只会前进 m 次，回退 m 次，复杂度只与 n+m 成正比。

KMP 匹配的完整过程

代码结构如下：

void KMP(string t, string s)
{
    int n = t.size(), m = s.size();
    vector<int> pi = prefix_function(s);

    int j = 0; // 当前匹配长度
    for(int i = 0; i < n; i++)
    {
        while(j > 0 && t[i] != s[j]) 
            j = pi[j - 1];

        if(t[i] == s[j]) j++;

        if(j == m)
        {
            cout << "Found at index " << i - m + 1 << endl;
            j = pi[j - 1]; // 继续寻找下一个出现
        }
    }
}

匹配流程总结

  1. 遍历文本串的指针 i
  2. 同时维护模式串指针 j
  3. 失配时不回到模式串开头，而是利用 pi[j - 1] 快速跳转
  4. 当 j == m，说明找到一个匹配的位置

时间复杂度 O(n+m) 。

完整实例程序

#include <bits/stdc++.h>
using namespace std;

vector<int> prefix_function(string s)
{
    int m = s.size();
    vector<int> pi(m, 0);
    for(int i = 1; i < m; i++)
    {
        int j = pi[i - 1];
        while(j > 0 && s[i] != s[j]) j = pi[j - 1];
        if(s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

void KMP(string t, string s)
{
    int n = t.size(), m = s.size();
    vector<int> pi = prefix_function(s);

    int j = 0;
    for(int i = 0; i < n; i++)
    {
        while(j > 0 && t[i] != s[j]) j = pi[j - 1];
        if(t[i] == s[j]) j++;
        if(j == m)
        {
            cout << "Found at index " << i - m + 1 << endl;
            j = pi[j - 1];
        }
    }
}

int main()
{
    string t = "ababcabcacbab";
    string s = "abcac";
    KMP(t, s);
}

展开

运行结果：

Found at index 5

与朴素算法一致，但效率提升巨大。

Part 3# 总结

KMP 的优化来自两个核心观察：

  1. 利用前缀数组避免不必要的回退
  2. 匹配失败时可以继续利用部分已匹配的信息

通过一次 O(m) 的预处理，将整体匹配时间降到 O(n+m) ，这是 KMP 的思想精髓。

但如果你理解了前缀数组的意义，KMP 就不再复杂，它只是在用非常聪明的方式记录 “已经匹配过的前缀信息”。

由chat-gpt5润色
\LaTeX \textbf{used}

3 个赞