标签：后缀 int nx fa Prefix ans 300005 Suffixes
- 为什么求Z函数的过程又被称为【扩展KMP】呢？因为KMP算法是可以求出哪些后缀能与前缀完全匹配的，而Z函数则对于那些不能完全匹配的后缀，求出了最大的匹配长度
- 现在你已经将问题转化为：在未被标记的后缀中，快速锁定当前新增的字符会使得哪些后缀失配
- “未被标记”太抽象了，回溯这个条件——在【当前能与前缀完全匹配的后缀中】，这不就是【KMP】求的东西嘛！
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int s[300005],a[300005],b[300005];
int nx[300005],fa[300005];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin>>n;
long long sum=0,ans=0;
for(int i=1;i<=n;i++)
{
cin>>s[i]>>a[i]>>b[i];
s[i]=(s[i]+ans)%n;
if(fa[i-1]&&s[fa[i-1]+1]==s[i])
{
fa[i-1]=fa[fa[i-1]];//要等s[i]出现以后才能判断
}
sum+=b[i];
if(i==1)
{
nx[1]=0;
fa[1]=0;
}
else
{
int j=nx[i-1];
while(j&&s[j+1]!=s[i])
{
j=nx[j];
}
if(s[j+1]==s[i])
{
j++;
}
nx[i]=j;
fa[i]=j;
}
int j=nx[i-1];
while(1)
{
if(s[j+1]!=s[i])
{
int id=i-j;
sum-=b[id];
if(j==0)
{
break;
}
j=nx[j];
}
else
{
if(j==0)
{
break;
}
j=fa[j];
}
}
ans=ans+sum*a[i];
cout<<ans<<"\n";
}
return 0;
}
标签：后缀,
int,
nx,
fa,
Prefix,
ans,
300005,
Suffixes
From： https://www.cnblogs.com/watersail/p/18432137