KMP - LeAf146

LeAf146

公告

叶子的博客，随便看看吧。

Learn More

标签

服务器网络字符串 ACM Agnet AI Blog Blogging codeforces

1769 字

6 分钟

KMP

2026-07-31

ACM

Blog

/

ACM

/

字符串

问题导入#

给定一个文本串 $S$ 和一个模式串 $P$ ，在 $S$ 中找到所有 $P$ 出现过的位置。

暴力匹配算法#

想当然地考虑，我们可以从 $S$ 的第一个字符开始，逐个与 $P$ 的字符比较，如果相同，则继续比较下一个字符，否则从 $S$ 的下一个字符开始重新比较。

实现如下：

1
vector<int> match(string S, string P) {
2
    int n = S.size(), m = P.size(), i = 0, j = 0;
3
    vector<int> ans;
4
    while (i < n) {
5
        if (S[i] == P[j]) {
6
            i++;
7
            j++;
8
            if (j == m) {
9
                ans.push_back(i - m);
10
                i -= j - 1;
11
                j = 0;
12
            }
13
        } else {
14
            i -= j - 1;
15
            j = 0;
16
        }
17
    }
18
    return ans;
19
}

易得，暴力匹配算法的时间复杂度为 $O(mn)$ 。

KMP 算法#

首先，我们注意到，在暴力匹配算法中，在最坏情况下，每次匹配失败后，我们都要回退到 $i-j+1$ 这个位置来重新匹配。而此时我们实际上已经知道了 $S[i-j+1\dots i]$ 的所有信息，我们完全没有必要重新获取一遍这些信息。换句话说，我们能不能做到不让 $i$ 指针左移？

举例：对于主串 $S=\text{abababc}$ 和模式串 $T=\text{ababc}$ ，当我们比较 $S[4]\neq T[4]$ 时，对于暴力匹配算法，我们接下来会比较 $S[1]$ 和 $T[0]$ 。而事实上，我们已经知道了 $S[0\dots 3]$ 和 $T$ 的全部内容，经过观察，我们发现只需要继续比较 $S[4]$ 和 $T[2]$ 即可，因为 $S[2,3]$ 和 $T[0,1]$ 是完全匹配的。那我们要怎么让计算机知道这件事呢？

先假设我们有一个神奇数组 magic，它可以告诉我们，如果我们匹配失败了，根据已知信息，我们可以跳过多少字符，直接开始下一个字符的比较。用更书面化的语言来说，这个神奇数组告诉了我们在当前匹配失败后，模式串指针可以跳转到哪里，保证前面的字符都是匹配的。

此时借助这个神奇数组和一些想当然，就可以得出以下算法：

1
vector<int> kmp(string S, string P) {
2
    vector<int> ans;
3
    vector<int> magic;
4
    int n = S.size(), m = P.size(), i = 0, j = 0;
5
    while (i < n) {
6
        if (S[i] == P[j]) {
7
            i++;
8
            j++;
9
            if (j == m) {
10
                ans.push_back(i - m);
11
                j = magic[j];
12
                // 如果我们对模式串匹配成功了，可以假设是在模式串末尾加一个与任意字符都匹配失败的字符，对应的神奇数组跳转到的位置保证前面的字符都是匹配的。
13
            }
14
        } else {
15
            if (j > 0)
16
                j = magic[j];
17
            else
18
                i++;
19
                // 如果我们第一个字符就匹配失败了，那就只能从主串中下一个位置继续开始了
20
        }
21
    }
22
    return ans;
23
}

由于主串指针的单调性，KMP 算法的时间复杂度是 $O(n)$ 的。

显然我们不能只靠假设就得出来神奇数组，做事情是要有根据的。

前缀函数#

在学习怎么求神奇数组前，我们需要一点前置知识：前缀函数。

给定一个长度为 $N$ 的字符串 $S$ ，其前缀函数定义为一个长度为 $N$ 的数组 $\pi$ ，其中 $\pi[i]$ 被定义为子串 $S[0\dots i]$ 的最长的相等的真前缀与真后缀的长度。详尽具体的定义见前缀函数。

这里直接给出最优算法，详细推导证明省略。我们需要知道，这个算法可以在 $O(N)$ 的时间求得一个字符串的前缀函数。

1
vector<int> prefix_function(string s){
2
    int n=s.size();
3
    vector<int> pi(n);
4
    for(int i=1;i<n;i++){
5
        int j=pi[i-1];
6
        while(j>0&&s[i]!=s[j])j=pi[j-1];
7
        if(s[i]==s[j])j++;
8
        pi[i]=j;
9
    }
10
    return pi;
11
}

注意到，如果一个字符串的前缀 $S[0\dots k-1]$ 和后缀 $S[N-k \dots N-1]$ 完全相同，在主串和模式串的匹配中，就可以借此性质来实现神奇数组的功能。对于模式串指针 $j$ ，当我们在匹配失败时，若有 $P[0\dots k-1]$ 和 $P[j-k\dots j-1]$ 完全相同，那就可以跳过这一部分，直接在当前位置继续匹配 $P[k]$ 。

失配函数#

在 KMP 算法中，我们把所谓的神奇数组叫做失配函数，通常指的是 KMP 匹配失败时，模式串应该跳转到哪里，常写成 next[i]、fail[i] 等形式。

从数值上来说，显然，我们有 $fail[i]=\pi[i-1]$ 。

举例：对于模式串 $P=\text{ababaca}$ ，它的前缀函数为 $\pi_{P}=\{0,0,1,2,3,0,1\}$ ，它的失配函数为 $fail_{P}=\{-1,0,0,1,2,3,0,1\}$ 。

我们令 $fail[0]=-1$ 表示对于主串当前位置的匹配彻底失败，应该从下一个位置再重新开始匹配。也可以想象成在模式串前面加一个与任意字符都匹配的字符。而 $fail[n]$ 则表示的是我们匹配成功后可以直接跳转到 $fail[n]$ 处开始新的一轮匹配，而不一定要从第一位开始。

失配函数的求法可以先求出前缀函数再移项得到，也可以想象成模式串自己与自己匹配。类比 KMP 算法代码可以得出：

1
vector<int> failure_function(string s){
2
    int n=s.size();
3
    vector<int> fail(n+1);
4
    fail[0]=-1;
5
    int i=0,j=-1;
6
    while(i<n){
7
        if(j==-1||s[i]==s[j]){
8
            i++;
9
            j++;
10
            fail[i]=j;
11
        }else j=fail[j];
12
    }
13
    return fail;
14
}

易得，求解失配函数的时间复杂度是 $O(n)$ 的。

算法模板#

结合以上内容，我们可以得到一份 KMP 算法模板，综合来看，时间复杂度是 $O(m+n)$ 的。

1
vector<int> failure_function(string s){
2
    int n=s.size();
3
    vector<int> fail(n+1);
4
    fail[0]=-1;
5
    int i=0,j=-1;
6
    while(i<n){
7
        if(j==-1||s[i]==s[j]){
8
            i++;
9
            j++;
10
            fail[i]=j;
11
        }else j=fail[j];
12
    }
13
    return fail;
14
}
15
vector<int> kmp(string S, string P) {
16
    vector<int> ans;
17
    vector<int> fail=failure_function(P);
18
    int n = S.size(), m = P.size(), i = 0, j = 0;
19
    while (i < n) {
20
        if (S[i] == P[j]) {
21
            i++;
22
            j++;
23
            if (j == m) {
24
                ans.push_back(i - m);
25
                j = fail[j];
26
            }
27
        } else {
28
            if (j > 0)
29
                j = fail[j];
30
            else
31
                i++;
32
        }
33
    }
34
    return ans;
35
}