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

· · 题解

更木棒的体验 \to George1123

题面

洛谷P5410 【模板】扩展 KMP（Z 函数）

给定两个字符串 a,b，要求出两个数组：b 的 z 函数数组 z、b 与 a 的每一个后缀的 LCP 长度数组 p。

数据范围：1\le |a|,|b|\le 2\times 10^7。

蒟蒻语

别的题解为什么代码那么长、讲解那么复杂？蒟蒻不解，写篇易懂一点的，希望没有错误理解。

注意：蒟蒻的下标是从 0 开始的。

蒟蒻解

定义 z(i) (i>0)：后缀 i 与字符串的 LCP 长度，劝退一点地说：

z(i)=\max_{len=1}^{|s|-i} \left(len\cdot [\forall 0\le x<len,s[(0)+(x)]=s[(i)+(x)]]\right)

对于求字符串 s 的 z 函数，可以用递推解决一部分问题，蒟蒻先放上精美的代码：

这里特定 z(0)=0（题目中 z(0)=|s|）。

void getz(string s){
    int l=0;
    R(i,1,sz(s)){
        if(l+z[l]>i) z[i]=min(z[i-l],l+z[l]-i);
        while(i+z[i]<sz(s)&&s[z[i]]==s[i+z[i]]) z[i]++;
        if(i+z[i]>l+z[l]) l=i;
    }
    // R(i,0,sz(s)) cout<<z[i]<<" ";cout<<'\n';
}

结论： 对于 i>0，对任意 0\le l<i 都可以递推得：

\forall 0\le x<\min(z(i-l),l+z(l)-i),s[(i)+(x)]=s[(0)+(x)]

证明：

\begin{aligned} &s[(i)+(x)]\\ =&s[(l)+(i+x-l)]\\ =&s[(0)+(i+x-l)]\color{red}{(x\le l+z(l)-i)}\\ =&s[(i-l)+(x)]\\ =&s[(0)+(x)]\color{red}{(x\le z(i-l))}\\ \end{aligned}

所以可以选定某个 0\le l<i，初始化 z(i)=\min(z(i-l),l+z(l)-i)，然后暴力判断字符相等增加 z(i)。

这里 l 选满足 j+z(j)(0\le j<i) 最大的 j，这样每个字符只会被暴力判断一次，所以时间复杂度可以做到 \Theta(n)。

对于题目中的问题其实把 b 和 a 接起来做个 z 就可以了。

代码

#include <bits/stdc++.h>
using namespace std;

//Start
typedef long long ll;
typedef double db;
#define mp(a,b) make_pair((a),(b))
#define x first
#define y second
#define Be begin()
#define En end()
#define sz(a) int((a).size())
#define pb(a) push_back(a)
#define R(i,a,b) for(int i=(a),I=(b);i<I;i++)
#define L(i,a,b) for(int i=(b)-1,I=(a)-1;i>I;i--)
const int iinf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;

//Data
const int N=2e7;
ll ansz,ansp;
string a,b;

//Zfunction
int z[N<<1];
void getz(string s){
    int l=0;
    R(i,1,sz(s)){
        if(l+z[l]>i) z[i]=min(z[i-l],l+z[l]-i);
        while(i+z[i]<sz(s)&&s[z[i]]==s[i+z[i]]) z[i]++;
        if(i+z[i]>l+z[l]) l=i;
    }
    // R(i,0,sz(s)) cout<<z[i]<<" ";cout<<'\n';
}

//Main
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>a>>b,getz(b+a);
    ansz^=1ll*(sz(b)+1)*(0+1);
    R(i,1,sz(b)) ansz^=1ll*(min(z[i],sz(b)-i)+1)*(i+1);
    R(i,0,sz(a)) ansp^=1ll*(min(z[i+sz(b)],sz(b))+1)*(i+1);
    cout<<ansz<<'\n'<<ansp<<'\n';
    return 0;
}

祝大家学习愉快！