\(Z\) 函数（扩展 KMP）

定义字符串 \(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;
}