JZTXT

KMP

发布时间 2023-07-25 20:11:11作者: 我是浣辰啦

引入

假设我们要在字符串 \(A\) 中找到字符串 \(B\)

先考虑暴力算法：

先将 \(A\) 与 \(B\) 的左端点对齐

如果匹配失败，就将字符串 \(B\) 向右移动一位，直到匹配成功为止

\[\begin{aligned} A &= a \ b \ a \ b \ a \ b \ a \ b \ c \\ B &= a \ b \ a \ b \ c \\ \end{aligned} \\ \begin{aligned} \\ A = a& \ b \ a \ b \ a \ b \ a \ b \ c \\ B =&\ a \ b \ a \ b \ c \end{aligned} \\ \begin{aligned} \\ A = a \ b&\ a \ b \ a \ b \ a \ b \ c \\ B =&\ a \ b \ a \ b \ c \end{aligned} \\ \begin{aligned} \\ A = a \ b\ a&\ b \ a \ b \ a\ b \ c \\ B =&\ a \ b \ a \ b \ c \end{aligned} \\ \begin{aligned} \\ A = a \ b\ a \ b&\ a \ b \ a\ b\ c \\ B =&\ a \ b \ a \ b \ c \end{aligned} \]

for (int i = 1, j = 0; i <= lens; ++i, j = 0) {
    while (j <= lenp && s[i] == p[j])
        ++j;

    if (j > lenp)
    	printf("%d\n", i);
}

当我们匹配失败时，我们忽略掉了一些很重要的信息

当第一次匹配失败时，两个划线串相等

\[\begin{aligned} A &= a \ b \ \underline{a \ b} \ a \ b \ a \\ B &= \underline{a \ b} \ a \ b \ c \end{aligned} \]

因此，我们下一次匹配时，就可以直接将两个字符串划线相同部分对齐，从而提升效率

对齐时，因为绿色部分相等，所以在判断时就不需要判断划线部分了

这就是 KMP 算法的思想

实现

我们用 \(nxt\) 数组存储每个位置下一步要跳到的地方

匹配的代码：

for (int i = 1, j = 0; i <= lens; ++i) {
    while (j && p[j + 1] != s[i])
        j = nxt[j]; // 如果失配，就不断往回跳，直到可以继续匹配

    if (p[j + 1] == s[i])
        ++j; // 如果匹配成功，那么模式串位置+1

    if (j == lenp) { // 匹配成功
        printf("%d\n", i - lenp + 1);
        j = nxt[j]; // 继续匹配
    }
}

但是现在我们要有一个问题，如何计算 \(nxt\) 数组？

我们考虑用模式串自己匹配自己

那么这个“自己匹配自己”该如何理解呢？

首先，在单次循环只有一个判断的原因在于每次至多向后多求一位的 \(nxt\)

其次，由于 \(j\) 是用于比对前后缀的，那么对于一组前后缀而言，第 \(i-1\) 和第 \(j-1\) 位之前均相同或者有不同，决定着 \(i\) 和 \(j\) 匹配的结果是从 \(0\) 开始还是基于上一个 \(j\) 继续自增代码：

for (int i = 2, j = 0; i <= lenp; ++i) {
    while (j && p[j + 1] != p[i])
        j = nxt[j];

    if (p[j + 1] == p[i])
        ++j;

    nxt[i] = j;
}

应用

字符串匹配

P3375 【模板】KMP字符串匹配

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;

char s[N], p[N];
int nxt[N];

int lens, lenp;

signed main() {
    scanf("%s%s", s + 1, p + 1);
    lens = strlen(s + 1), lenp = strlen(p + 1);

    for (int i = 2, j = 0; i <= lenp; ++i) {
        while (j && p[j + 1] != p[i])
            j = nxt[j];

        if (p[j + 1] == p[i])
            ++j;

        nxt[i] = j;
    }

    for (int i = 1, j = 0; i <= lens; ++i) {
        while (j && p[j + 1] != s[i])
            j = nxt[j];

        if (p[j + 1] == s[i])
            ++j;

        if (j == lenp) {
            printf("%d\n", i - lenp + 1);
            j = nxt[j];
        }
    }

    for (int i = 1; i <= lenp; ++i)
        printf("%d ", nxt[i]);

    return 0;
}

最小循环节

Power Strings

若 \((n - nxt_n) | n\) ，则最小循环节长度为 \(n - nxt_n\) ，否则为 \(n\) ，可以结合这张图感性理解

其中箭头表示两块字符串是相同的

当然也有可能不是这种情况，但是最小循环节的长度一定是 \(n - nxt_n\) 的因子（ \((n - nxt_n) | n\) ）

P4391 [BOI2009]Radio Transmission 无线传输

与上题类似

统计前缀出现次数

问题一：求每个前缀在该串中的出现次数

首先设 \(ans_i\) 为每个 \(nxt\) 值出现次数，如果我们知道长度为 \(i\) 的前缀出现了恰好 \(ans_i\) 次，那么其最长的既是前缀又是后缀的子串也会出现 \(ans_i\) 次，累加即可

最后对于原始的前缀出现位置，我们统一 \(+1\) 即可

for (int i = 1; i <= n; ++i)
	++ans[nxt[i]];

for (int i = n; i; --i)
	ans[nxt[i]] += ans[i];

for (int i = 1; i <= n; ++i)
	++ans[i];

问题二：求每个前缀在另一串中的出现次数

我们把两串拼起来，并在中间塞入一个无用字符，直接容斥即可

其他

P3435 [POI2006] OKR-Periods of Words

我们考虑最大周期代表什么，发现就是中间部分的循环节，为了让其最小，循环节就要最小，所以考虑进行跳 \(nxt\) 数组知道其后一个等于 \(0\)

发现直接跳会 TLE 了，所以考虑路径压缩，就是每次先将答案算好，之后再将这一段字符串跳的部分更新成当前答案

for (int i = 1; i <= n; ++i) {
	int tmp = i;
	
	while (nxt[ans])
		ans = nxt[ans];
	
	if (nxt[i])
		nxt[i] = ans;
	
	ans += i - tmp;
}