bzoj 3277: 串 & bzoj 3473: 字符串【后缀自动机||后缀数组】

墨蓝 2021-09-30 15:26 236阅读 0赞

建一个广义后缀自动机（每加完一个串都返回root），在parent树上dpsum记录合法长度，打着时间戳往上跳，最后每个串在自动机上跑一变统计答案即可。  
后缀数组理解起来可能方便一点，但是难写，就只说一下思路……把这些串加上特殊字符拼起来，然后按着sa扫，对每个位置二分长度，再左右端点（用height判断是否有k个）

#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=300005; int n,k; long long ans; string s[N]; struct sam { int a[N][27],fa[N],len[N],v[N],c[N]; long long sum[N]; int p,q,np,nq,la,cnt; sam() { la=++cnt; } void build(int c) { p=la; np=la=++cnt; len[np]=len[p]+1; while(!a[p][c]&&p) a[p][c]=np,p=fa[p]; if(!p) fa[np]=1; else { q=a[p][c]; if(len[q]==len[p]+1) fa[np]=q; else { nq=++cnt;len[nq]=len[p]+1; memcpy(a[nq],a[q],sizeof(a[q])); fa[nq]=fa[q]; fa[q]=fa[np]=nq; while(a[p][c]==q) a[p][c]=nq,p=fa[p]; } } } void clc(int x) { if(x==1||v[x]) return; v[x]=1; clc(fa[x]); sum[x]+=sum[fa[x]]; } }sam; int main() { // freopen("string.in","r",stdin); // freopen("string.out","w",stdout); ios::sync_with_stdio(false); cin>>n>>k; for(int i=1;i<=n;i++) { cin>>s[i]; for(int j=0;j<s[i].length();j++) sam.build(s[i][j]-'a'); sam.la=1; } for(int i=1;i<=n;i++) { int x=1,now=i; for(int j=0;j<s[i].length();j++) { x=sam.a[x][s[i][j]-'a']; int t=x; while(t&&sam.v[t]!=now) sam.v[t]=now,sam.c[t]++,t=sam.fa[t]; } } for(int i=1;i<=sam.cnt;i++) sam.v[i]=0; for(int i=1;i<=sam.cnt;i++) sam.sum[i]=(sam.c[i]>=k)*(sam.len[i]-sam.len[sam.fa[i]]); for(int i=1;i<=sam.cnt;i++) sam.clc(i); for(int i=1;i<=n;i++) { int x=1;ans=0; for(int j=0;j<s[i].length();j++) x=sam.a[x][s[i][j]-'a'],ans+=sam.sum[x]; cout<<ans<<endl;; } return 0; }

转载于:https://www.cnblogs.com/lokiii/p/9695861.html