板子 kmp

利用 nxt 数组使字符串匹配降到 \(O(n)\)。

next

i从2开始，j从0开始

i和j+1匹配不上，j跳nxt

匹配就j++

nxt[i] = j

for (int i = 2, j = 0; i <= blen; ++i) {
    while (j && b[j+1] != b[i])
        j = nxt[j];
    if (b[j+1] == b[i])
        ++j;
    nxt[i] = j;
}

匹配

i从a的1-len，j从0开始

a[i]和b[j+1]匹配不上就j跳nxt

否则j++

j到blen则匹配完一次，跳nxt

for (int i = 1, j = 0; i <= alen; ++i) {
    while (j && b[j+1] != a[i])
        j = nxt[j];
    if (b[j+1] == a[i])
        ++j;
    if (j == blen) {
        printf("%d\n", i - blen + 1);
        ans++;
        j = nxt[j];
    }
}

---

以上为远古文章。

扩展 kmp

板子题

给出长为 \(n\) 的字符串 \(s\)。

\(\mathcal O(n)\) 处理 \(z\) 函数：\(z_i=|\operatorname{LCP}(s,s[i:])|\)。

记录 \(r\) 最大的一对 \(l,r\) 满足 \(r=l+z_l-1\)。

设从前到后处理到 \(i\)，当 \(i\le r\) 时，初始化 \(z_i=\min\{z_{i-l+1},-i+1\}\)，否则为 \(0\)。

然后暴力匹配 \(s[i+z_i]\) 和 \(z[z_i+1]\)。

每个字符最多被暴力匹配 \(1\) 次，复杂度 \(\mathcal O(n)\)。

z[1] = n;
int l = 0, r = 0;
for (int i = 2; i <= n; ++i) {
    if (i <= r) z[i] = min(z[i - l + 1], r - i + 1);
    while (i + z[i] <= n && s[z[i] + 1] == s[i + z[i]]) ++z[i];
    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
}