扩展 KMP / $Z$ 函数

定义字符串 $s$ 的 $Z$ 函数 $z(i)$ 表示 $s$ 的 $[i,n)$ 后缀和 $s$ 的最长公共前缀长度（lcp）。

$Z$ 函数有 $O(n)$ 求法。匹配字符串时，我们可以将模式串和文本串拼接（中间添加分隔符），求出 $t+s$ 的 $Z$ 函数。如果某个 $s$ 的后缀和 $t+s$ 的 lcp 等于 $len(t)$，则该位置匹配。$Z$ 函数还可以用来求 border：枚举每个后缀，判断其是否为 border。

$Z$ 函数的线性求法

我们从左往右处理每个位置的 $Z$ 函数，保证在处理 $i$ 时 $[0,i)$ 的 Z 函数都已经求得。其线性时间复杂度得益于每次都从 $j+z[j]$ 取到最大值的 $k$ 处转移，并且 $\max\{j+z[j]\}$ 增量不超过 $n$。

如图，我们从左往右遍历字符串。当前考虑位置 $i$，$k$ 为 $k+z[k]$ 最大的 $k$。如果 $k+z[k]\ge i$，我们可以通过 $z[k]$ 将 $i$ 转移到 $i-k$，再通过 $z[i-k]$ 求出 $z[i]$ 的下界。注意：求出的下界不能超过 $k+z[k]-i$，因为超出的部分不能通过 $z[k]$ 转移。

求出下界之后，直接暴力扩展即可。如果下界小于 $k+z[k]-i$，则一定不会成功扩展（否则 $z[i-k]$ 不是最优解），即不会产生时间复杂度。如果成功扩展，则有扩展后的 $i+z[i]>k+z[k]$，$i$ 成为新的 $k$，可以直接均摊在 $\max\{j+z[j]\}$ 的增量上。

注意：如果初值 $z[0]$ 赋为 $n$，则后面扩展时会出现问题。因此 $z[0]$ 应赋为 $0$，初始 $k=0$。

for(int i = 1, k = 0; i < s.size(); i++) {
    if(k + z[k] > i) z[i] = min(z[i - k], k + z[k] - i); // 求出下界
    while(i + z[i] < s.size() && s[i + z[i]] == s[z[i]]) ++z[i]; // 暴力扩展
    if(i + z[i] > k + z[k]) k = i; // 更新 k
}

P5410 【模板】扩展 KMP/exKMP（Z 函数）

模板代码

#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N = 2E7 + 10;

int n, m, ans1, ans2;
string a, b;

int z[N * 2];

signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> a >> b;
    n = a.size(), m = b.size();

    b += '$' + a;
    for(int i = 1, k = 0; i < b.size(); i++) {
        if(k + z[k] > i) z[i] = min(z[i - k], k + z[k] - i);
        while(i + z[i] < b.size() && b[i + z[i]] == b[z[i]]) ++z[i];
        if(i + z[i] > k + z[k]) k = i;
    }

    ans1 ^= m + 1;
    for(int i = 1; i < m; i++) {
        ans1 ^= (i + 1) * (z[i] + 1);
    }
    for(int i = m + 1; i < n + m + 1; i++) {
        ans2 ^= (i - m) * (z[i] + 1);
    }

    cout << ans1 << '\n' << ans2 << endl;

    return 0;
}

CF126B Password

题目大意

给定字符串 $S$（$|S|\le 10^6$），求既是 $S$ 的前缀又是 $S$ 的后缀同时又在 $S$ 中间出现过的最长子串。

我们先用 $Z$ 函数求出 既是前缀 又在中间出现过的子串的 长度的最大值。不难发现小于这个长度的前缀也都是合法的中间段。具体的，先求出 $Z$ 函数，然后求出

$$mx=\max\big\{z[i]-[i+z[i]=n]\big\}$$

接着我们找出长度小于等于 $mx$ 的最长 border 就是答案。

代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1E6 + 10;

int n, mx, ans, ap;
string s;

int z[N];

int main() {

    cin >> s;
    n = s.size();

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

    for(int i = 1; i < n; i++) {
        mx = max(mx, z[i] - (i + z[i] == n));
    }

    for(int i = 1; i < n; i++) {
        if(i + z[i] == n && z[i] <= mx) ans = max(ans, z[i]);
    }

    for(int i = 0; i < ans; i++) {
        cout << s[i];
    }
    if(!ans) cout << "Just a legend";
    cout << endl;

    return 0;
}

CF432D Prefixes and Suffixes

题目大意

给定一个字符串 $S$，输出所有 border 长度，和每个 border 在字符串中出现的次数。

由于 border 都是前缀，所以问题归约为求出每一个前缀出现的次数。到这里已经可以使用 KMP 解决了。这里介绍一种使用 $Z$ 函数的做法。考虑字符串的下标 $i$，以 $i$ 开头的子串对 $\big[0,z[i]\big)$ 的前缀都有贡献。我们统计出 $z[i]$ 对应的桶数组，然后做后缀和即可。

代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1E5 + 10;

int n;
int z[N], cnt[N];
string s;

int pos[N], nn;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> s;
    n = s.size();

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

    z[0] = n;
    for(int i = 0; i < n; i++) {
        cnt[z[i]]++;
    }
    for(int i = n; i > 0; i--) {
        cnt[i - 1] += cnt[i];
    }

    for(int i = n - 1; i >= 0; i--) {
        if(i + z[i] == n) pos[++nn] = z[i];
    }

    cout << nn << '\n';
    for(int i = 1; i <= nn; i++) {
        cout << pos[i] << ' ' << cnt[pos[i]] << '\n';
    }

    return 0;
}