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

题目描述

给定两个字符串 $a,b$，你要求出两个数组：

• $b$ 的 $z$ 函数数组 $z$，即 $b$ 与 $b$ 的每一个后缀的 LCP 长度。
• $b$ 与 $a$ 的每一个后缀的 LCP 长度数组 $p$。

对于一个长度为 $n$ 的数组 $a$，设其权值为 $\operatorname{xor}_{i=1}^n i \times (a_i + 1)$。

输入格式

两行两个字符串 $a,b$。

输出格式

第一行一个整数，表示 $z$ 的权值。

第二行一个整数，表示 $p$ 的权值。

输入输出样例 #1

输入 #1

aaaabaa
aaaaa

输出 #1

6
21

说明/提示

样例解释：

$z = {5\ 4\ 3\ 2\ 1}$，$p = {4\ 3\ 2\ 1\ 0\ 2\ 1}$。

---

数据范围：

对于第一个测试点，$|a|,|b| \le 2 \times 10^3$。

对于第二个测试点，$|a|,|b| \le 2 \times 10^5$。

对于 $100\%$ 的数据，$1 \le |a|,|b| \le 2 \times 10^7$，所有字符均为小写字母。

思路

Z 函数用于求原字符串与每个后缀的最大匹配长度。$z[1]=n$。遍历位置 i 时，如果 i 位于之前的匹配盒子 $[l,r]$ 内，就从对应位置 $z[i−l+1]$ 继承，但最多继承 $r−i+1$ 个字符；然后继续暴力扩展，并更新最靠右的匹配盒子。

GPT Said

z函数用于求解原字符串和它的每个后缀的最长公共前缀长度。
$z[1]$是完全匹配的，所以默认就是字符串长度。
然后开始遍历，计算过程中维护$[l,r]$，满足$s[l…r]$与字符串前缀相同。遍历到位置i时，如果$i<=r$，说明$i$在已知匹配区间内，可以先令 $z[i]=min(z[i-l+1],r-i+1)$ 继承已经确定的匹配长度；如果$i>r$，则$z[i]=0$开始。随后继续逐字符暴力比较，扩展$z[i]$。如果当前匹配区间$[i,i+z[i]-1]$的右端点超过了$r$，就更新
$l=i$ , $r=i+z[i]-1$

for (int i = 2; i <= n; i++) {
    // 1. 继承
    if (i <= r) {
        z[i] = min(z[i - l + 1], r - i + 1);
    }

    // 2. 暴力扩展
    while (i + z[i] <= n &&
           s[i + z[i]] == s[1 + z[i]]) {
        z[i]++;
    }

    // 3. 更新盒子
    if (i + z[i] - 1 > r) {
        l = i;
        r = i + z[i] - 1;
    }
}

最简记忆：

i 在盒子内 → 先继承
继承不能越过 r → 取 min
然后继续比较 → 暴力扩展
扩展得更远 → 更新 [l,r]

代码

//Sunshine sunshine ladybugs awake,
//Clap your hooves and do a little shack.
#include<bits/stdc++.h>
#define int long long
#define endl "\n"

using namespace std;

using PII=pair<int,int> ;
const int MAXN=300005;
const int mod=998244353;
const int INF=0x3f3f3f3f3f3f3f3f;

void solve(){
    string a,b;
    cin>>a>>b;

    a=" "+a;
    b=" "+b;

    int n=(int)a.size()-1;
    int m=(int)b.size()-1;

    vector<int> z(m+1);
    z[1]=m;

    int l=1,r=0;

    for(int i=2;i<=m;i++){
        if(i<=r){
            int k=i-l+1;
            int remain=r-i+1;

            z[i]=min(z[k],remain);
        }

        while(i+z[i]<=m&&
              b[1+z[i]]==b[i+z[i]]){
            z[i]++;
        }

        if(z[i]>0&&i+z[i]-1>r){
            l=i;
            r=i+z[i]-1;
        }
    }

    int answerZ=0;
    for(int i=1;i<=m;i++){
        answerZ^=1ll*i*(z[i]+1);
    }



    int answerP=0;
    l=1;r=0;
    for(int i=1;i<=n;i++){
        int now=0;
        if(i<=r){
            int k=i-l+1;
            int remain=r-i+1;
            now=min(z[k],remain);
        }

        while(now<m&&
              i+now<=n&&
              a[i+now]==b[1+now]){
            now++;
        }

        if(now>0&&i+now-1>r){
            l=i;
            r=i+now-1;
        }

        answerP^=1ll*i*(now+1);
    }

    cout<<answerZ<<endl;
    cout<<answerP<<endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t;cin>>t;while(t--)
    solve();
    return 0;
}