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

· · 题解

太菜了，今天才刚学会。

题目链接。

Z 函数 定义

对于一个长度为 n 的字符串 s，定义函数 z[i] 表示 s 和 s[i,n-1]（即以

——OI Wiki

Solution

Part 1 暴力碾标算

考虑暴力，很容易可以想道 O(n^2) 的做法：

z[1]=strlen(s+1);
for(int i=2;i<=strlen(s+1);i++){
    for(int j=1,k=i;k<=strlen(s+1);k++,j++){
        if(s[j]!=s[k]){ 
            z[i]=j-1;
            break;
        }
        z[i]=j; 
    }
}

只能拿到 29 分。

Part 2 正解

考虑跟 Manacher 一样的思路：

（S_1 表示原字符串 s，S_i 表示以第 i 个字符为开头的 S 后缀，S_{max} 表示与 S 的 LCP 最长的后缀）。

我们规定红色线段为 S 后缀中 LCP 的右端点目前最远的 LCP。

那么 r 表示右端点，l 表示左端点。

再解释一下。

设以红色线段为 LCP 的后缀为 S_{max}，以第 j 个节点为开头的后缀为 S_j，一个后缀 s 的 LCP 右端点为 R_{s} 左端点为 L_{s}，则：

R_{S_{max}} = \max_{j }^{i-1} R_{S_j} r=R_{S_{max}},l=L_{S_{max}}

那么我们这的绿色线段表示以 i 为左端点，r 为右端点的 S 子串。

可以发现 S 会有一段相对应的绿色线段，由于与 S_{max} 相对应，所以左端点为 l-i+1。

那么就肯定会有一个后缀 S_{l-i+1} 使得前缀为绿色线段，那么 S_i 的 Z 函数就可已从 S_{l-i+1} 来转移，因为 S_{l-i+1} 与 S_i 都是绿色前缀。

类似 Manacher 算法，我们分为两种情况：

继承后，我们再暴力一下，得到准确的答案。

最后还需要更新下 r 与 l。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e7+10;
char a[N],b[N];
int ans;
int z[N];
int p[N];
signed main(){
    ios::sync_with_stdio(false);
    cin>>(a+1)>>(b+1);
    int l=0,r=0;
    z[1]=strlen(b+1);
    for(int i=2;i<=strlen(b+1);i++){
        if(i<r) z[i]=min(z[i-l+1],r-i+1);
        while(i+z[i]<=strlen(b+1)&&b[i+z[i]]==b[z[i]+1]) {
            z[i]++;
        }
        if(r<i+z[i]-1){
            r=i+z[i]-1;
            l=i;
        }
    }
    for(int i=1;i<=strlen(b+1);i++){
        ans=ans^(i*(z[i]+1));
    }
    cout<<ans<<endl;
    l=0,r=0;
    for(int i=1;i<=strlen(a+1);i++){
        if(i<r) p[i]=min(z[i-l+1],r-i+1);
        while(i+p[i]<=strlen(a+1)&&a[i+p[i]]==b[p[i]+1]) {
            p[i]++;
        }
        if(r<i+p[i]-1){
            r=i+p[i]-1;
            l=i;
        }
    }
    ans=0;
    for(int i=1;i<=strlen(a+1);i++){
        ans^=(i*(p[i]+1));
    }
    cout<<ans;
}