KMP

发表于 更新于 阅读次数： 本文字数： 2.7k 阅读时长 ≈ 5 分钟

前置概念

$Border$：如果字符串同长度的前缀与后缀相同，称该前缀(后缀)是一个$Border$(可以指这个前缀也可以指这个前缀的长度)
循环周期：对于字符串$S$和正整数$p$，如果有$S_i=S_{i-p}$，对于$p\lt i\leq |S|$成立，称$p$是$S$的一个循环周期
循环节：若字符串$S$的周期$p$满足$p\mid |S|$，称$p$是$S$的一个循环节

重要性质$1$：$p$是$S$的周期$\Leftrightarrow |S| - p$是$S$的$Border$

因此求$Border$问题与求周期问题等价

重要性质$2$：$S$的$Border$的$Border$也是$S$的$Border$

因此求$S$的所有$Border$等价于求最大$Border$(求完最大$Border$变为子问题)

$Next$数组

$nxt_i$的值为$prefix_i$的非平凡最大$Border$
记$nxt_1=0$
考虑$prefix_i$的非平凡最大$Border$，去掉最后一个字符，就是$prefix_{i-1}$的非平凡最大$Border$
但反过来，$prefix_{i-1}$的非平凡最大$Border$加上一个字符，不一定是$prefix_i$的非平凡最大$Border$($S_i$与$S_{nxt_{i-1}+1}$不一定相等)
因此想求$nxt_i$，需遍历$prefix_{i-1}$的所有非平凡$Border$，结合重要性质$2$，发现这个过程等价于去遍历$nxt_{i-1},nxt_{nxt_{i-1}},\cdots,0$
从大到小遍历，如果某一个$Border$加上后一个字符满足相等，就可以及时$break$

求$Next$数组代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void get_nxt()
{
    nxt[1] = 0;
    for (int i = 2; i <= m; ++i)
    {
        int j = i - 1;
        while (j != 0)
        {
            if (t[i] == t[nxt[j] + 1])
            {
                nxt[i] = nxt[j] + 1;
                break;
            }
            j = nxt[j];
        }
    }
}

求$Next$数组复杂度分析

考虑势能分析
如果$nxt_i=nxt_{i-1}+1$，势能增加$1$
否则势能会先减少到某个$nxt_j$，然后有$nxt_i=nxt_j+1$，在寻找$nxt_j$的过程中，势能减少，每次至少减少$1$，寻找结束后势能加$1$
如果一直到$j=0$都没有找到满足的$nxt_j$，说明$nxt_i=0$，势能清空
综上，势能总量为$O(N)$，时间复杂度就是$O(N)$，常数不超过$2$

$KMP$思想

$Next$数组记录了每个位置的前缀的非平凡最大$Border$信息
利用这个信息可以加速字符串匹配
先看暴力匹配为什么慢

1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 1, j = 1; i <= n; )
{
    if (s[i] == t[j])
        ++i, ++j;
    else
        i = (i - 1) - (j - 1) + 1 + 1, j = 1;
    if (j == m + 1)
    {
        std::cout << (i - 1) - m + 1 << '\n';
        i = i - m + 2, j = 1;
    }
}

暴力匹配的时间瓶颈在于：当遇到匹配失败的字符时，$i$和$j$大量的回溯
$KMP$算法首先预处理出模式串$t$的$Next$数组，然后基于这样一个事实节约时间：当遇到匹配失败的字符，$i$指针不需要动，尝试让$j$回溯到$prefix_{j-1}$所有$Border$的长度即可，非$Border$长度一定不会匹配的更“远”
“尝试让$j$回溯到$prefix_{j-1}$所有$Border$的长度”这个过程，结合重要性质$2$和已经预处理好的$Next$数组，其实还是一个在$Border$链上跳的过程
结合势能分析，复杂度为$O(N+M)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for (int i = 1, j = 1; i <= n; )
{
    if (s[i] == t[j])
        ++i, ++j;
    else // 遇到匹配失败的字符，在Border链上跳
        while (j != 1 && s[i] != t[j]) 
            j = nxt[j - 1] + 1;
    if (j == 1 && s[i] != t[j]) // 如果到1了还是失败，说明这个位置不可能
        ++i;
    if (j == m + 1)
    {
        std::cout << (i - 1) - (j - 1) + 1 << '\n';
        j = nxt[m] + 1;
    }
}

$KMP$模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
struct KMP {
    std::vector<int> nxt;
    std::string s, t;
    int n, m;
    KMP(std::string a, std::string b) : s("?" + a), t("?" + b) {
        n = s.length() - 1, m = t.length() - 1;
        nxt.resize(m + 1);
        nxt[1] = 0;
        for (int i = 2; i <= m; ++i) {
            int j = i - 1;
            while (j != 0) {
                if (t[i] == t[nxt[j] + 1]) {
                    nxt[i] = nxt[j] + 1;
                    break;
                }
                j = nxt[j];
            }
        }
    }
    std::vector<int> get_start_pos(bool start_from_zero) {
        std::vector<int> res;
        for (int i = 1, j = 1; i <= n; ) {
            if (s[i] == t[j])
                ++i, ++j;
            else
                while (j != 1 && s[i] != t[j]) 
                    j = nxt[j - 1] + 1;
            if (j == 1 && s[i] != t[j])
                ++i;
            if (j == m + 1) {
                res.push_back((i - 1) - (j - 1) + 1 + (start_from_zero ? -1 : 0));
                j = nxt[m] + 1;
            }
        }
        return res;
    }
};