前言

距离 2026 CSP 还有 4 天。

---

$\text{KMP}$ 字符匹配

KMP 可以在 $O(n+m)$ 内找出所有匹配的子串。

假设主串是 $s$，长度为 $n$。要匹配的字符串是 $t$，长度为 $m$。

暴力：$\textsf{「逐个匹配错误回溯法」}$

其实不是这个名字。

字面意思，逐个比较 $s$ 和 $t$ 的字符。如果失败了就把遍历 $s$ 的指针 $i$ 回溯到匹配前的下一个位置，$j$ 回到开头，重新匹配。

$\textsf{「最长公共前后缀」}$

即常说的 $next$ 数组。

字面意思，即一个字符串，有个前缀和后缀是相同的。例如 $\texttt{abcdabc}$，前缀 $\texttt{abc}$ 和后缀 $\texttt{abc}$ 相同（$\texttt{\color{red}abc\color{ordinary}d\color{red}abc}$），所以 $\texttt{abcdabc}$ 的最长公共前后缀就是 $\texttt{abc}$，长度为 $3$。同时最长公共前后缀不能是字符串本身，不然没有意义。

定义 $nxt_i$ 表示 $[0, i]$ 的最长公共前后缀长度。（下用 next 表示「最长公共前后缀」）

首先 $0$ 的 next 肯定是 $0$，因为 $[0,0]$ 只有一个字符，而 next 又不能是它本身。

★★★★★$「转移」$

首先看前一个字符的 next。前一个的 next 是 $2$。所以 $[0,2)$ 这段和 $[2,4)$ 这段是一样的。然后看两端后面紧接着的字符是否一样（后一段紧接着的字符其实就是指着的那个）。如果不一样的话，那可以继续往前找 next。直到一样，或者到头了。

示意图：

实际上，不断缩小希望的「最长公共前后缀」，检查是否相同。

void next(string str)
{
    int n = str.size();
    for (int i = 1; i < n; ++i)
    {
        int j = nxt[i];
        while (j && str[i] != str[j])
            j = nxt[j];

        if (str[i] == str[j])
            nxt[i + 1] = j + 1;
        else nxt[i + 1] = 0;
    }
}

$\text{KMP}$ 主体

还是看示意图吧：

将 $j$ 移动到 $nxt_j$，继续匹配。

当 $j=m$ 时，则匹配成功。

void KMP()
{
    next(t);
    int j = 0;
    for (int i = 0; i < n; ++i)
    {
        while (j && s[i] != t[j])
            j = nxt[j];

        if (s[i] == t[j]) ++j;
        if (j == m)
        {
            cout << i - m + 2 << '\n';
            j = nxt[j];
        }
    }
}