KMP

发表于 更新于 分类于

本文按照考研408的思路，从头开始给出KMP的推导，并给出一份简洁的KMP模板。

问题描述

字符串匹配问题，给定一个模板串p，询问p是不是s的子串。

暴力的思路是直白的，两个指针i和j从前往后进行扫描，效率是 \(O(MN)\) 。

1
2
3
4
5
6
7
8
9
int find(const string & s, const string & p) {
    for (int i = 0, j; i < s.length() - p.length(); ++i) {
        for (j = 0; j < p.length(); ++j) {
            if (s[i+j] != p[j]) break;
        }
        if (j == p.length())
            return i;
    }
}

算法本质可以用下面的表格描述：

0 1 2 3 4 5 6 7 8 9 10 11 12
s a b a b c a b c a c b a b
p a b c a c
a b c a c
a b c a c

前缀与后缀

暴力算法之所以效率低下，因为每次匹配失败都只向后移动一位。可是我们知道前面的部分都是成功匹配的，这个信息被“丢掉”了，那么能否利用这个信息就是关键。

这里我们定义字符串的前缀和后缀，前缀指从头开始的所有子串，后缀指以末尾结束的所有子串，这里的前缀和后缀都不包括字符串本身。

例如：字符串 \(abca\) 的前缀集合为 \(\lbrace a, ab, abc\rbrace\)， 后缀集合为 \(\lbrace a, ca, bca\rbrace\)。

下面定义部分匹配函数 \(PM\)，表示字符串的前缀集合与后缀集合的交集中最长的字符串长度。\(PM[j-1]\) 表示子串 \(p[0:j]\) 的前缀和后缀的最长公共匹配长度。

0 1 2 3 4
p a b c a c
pm 0 0 0 1 0

这个函数有什么意义？我们回到上面举的例子：

0 1 2 3 4 5 6 7 8 9 10 11 12
s a b a b c a b c a c b a b
p a b c a c
a b c a c
a b c a c

在这个例子中，当位置 2 的匹配失败后，此时 \(s\) 中的位置是 \(i=2\)，\(p\) 中的位置 \(j=2\)，移动一次是没有意义的，至少也要移动两次使得 \(p\) 的前缀和 \(s[0:i]\) 的后缀重合，不难发现，匹配失败后的移动次数有如下关系：

\[Move = j - PM[j-1]\]

0 1 2 3 4 5 6 7 8 9 10 11 12
s a b a b c a b c a c b a b
p a b c a c
a b c a c
a b c a c

为了方便使用，一般我们不直接使用 \(PM\) ，虽然它的数学意义很明显。我们定义 \(next[j] = PM[j-1]\)，相当于将整个 \(PM\) 右移一位，这样会空出来 \(next[0]\)，我们定义 \(next[0]=-1\)，它表示如果 \(j=0\) 匹配失败，右移一位。这样一来，我们可以得到非常简单的公式，当 \(j\) 位置匹配失败，新的 \(j\) 如下：

\[j \leftarrow j - Move = next[j]\]

代码如下：

1
2
3
4
5
6
7
8
9
10
int kmp_index(const string & s, const string & p, const vector<int> & next) {
    int j = 0;
    for (int i = 0; i < s.length(); ++i) {
        while (j != -1 && p[j] != s[i]) j = next[j];
        ++j;
        if (j == p.length())
            return i - j + 1;
    }
    return -1;
}

构造 next 函数

如何构造 \(next\) 函数成为的难点。一种理解是，将模板串 \(p\) 自己和自己匹配。

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> kmp_getnext(const string & p) {
    vector<int> next(p.length());
    next[0] = -1;
    int j = -1;
    for (int i = 0; i < p.length() - 1; ++i) {
        while (j != -1 && p[j] != p[i]) j = next[j];
        ++j;
        // next[i+1] = j;
        next[i+1] = p[i+1] == p[j] ? next[j] : j;
    }
    return next;
}

代码注释的地方是一处优化，以下面的字符串为例：

0 1 2 3 4 5 6
p a b a b a b c
pm 0 0 1 2 3 4 0
next -1 0 0 1 2 3 4
next' -1 0 -1 0 -1 0 4

当 \(j=2\) 匹配失败时，按理说应该转移到 \(j=0\)，但事实上因为 \(p[0]=p[2]\)，所以转移后一定仍然匹配失败，所以可以将相同字母的转移路径压缩。

不难发现构造 \(next\) 数组的过程和 KMP 的过程几乎一模一样，只是将 s 改成了 p 而已，所以可以视作 p 串的自我匹配。

所有匹配

朴素的 KMP 只能找到首个匹配的位置，如果想要找到所有匹配的位置呢？

其实改动非常小，p 串匹配完后，将答案记录下来，不要跳出，继续匹配。可是关键是 \(j\) 怎么转移？

仔细观察不难发现，\(next\) 是 \(PM\) 右移一位的结果，最后一个位置的 \(PM\) 值被丢掉了，如果我们没有舍弃它，其含义就是匹配完后 \(j\) 应该转移的结果，相当于在 p 串末尾添加了一个永远匹配失败的字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> kmp_all(const string & s, const string & p) {
    // get next
    vector<int> next(p.length() + 1);
    next[0] = -1;
    int j = -1;
    for (int i = 0; i < p.length(); ++i) {
        while (j != -1 && p[j] != p[i]) j = next[j];
        ++j;
        next[i+1] = p[i+1] == p[j] ? next[j] : j;
    }

    // get index
    vector<int> ans;
    j = 0;
    for (int i = 0; i < s.length(); ++i) {
        while (j != -1 && p[j] != s[i]) j = next[j];
        ++j;
        if (j == p.length()) {
            ans.push_back(i - j + 1);
            j = next[j];
        }
    }
    return ans;
}

效率分析

  • KMP 的改进就是 “母串不回溯”，容易发现 \(i\) 是单调增长的。
  • 对于 \(j\) 的分析并不是很容易，因为匹配失败后 \(j\) 沿着 fail 指针向前跳跃的次数无法得知，但是可以使用 均摊分析 ：
    • 每次成功匹配后 \(j\) 会 \(+1\) ；
    • \(j\) 增加的次数和母串的长度相当；
    • \(j\) 向前跳跃的次数不超过 \(j\) 的大小；
    • \(j\) 的变化也是 \(O(N)\) 级别的。
  • 综上所述，整个 KMP 的时间复杂度是 \(O(N+M)\)。