【BZOJ4566】【HAOI2016】找相同字符

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

后缀自动姬好，好写好调好ac

原题：

给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两

个子串中有一个位置不同。

1 <=n1, n2<= 20000

之前写了个后缀数组+并查集的，因为我只会后缀数组……

后看看dalao们纷纷使用后缀自动姬秒题，决定提高一下自己姿势水平，学一发后缀自动姬

然后根本无法理解啊quq，现在板子差不多理解了，但是自动姬上做DP的延伸还是不能理解quq

多做题应该就能理解了吧……

这题dp具体思路是啥我也没搞懂，直接上结论

每个点的贡献：|right(x)|*(max[x]-max[fa[x]])

具体贡献到答案上，就搞一个b在当前节点上匹配的公共长度l，然后对答案的贡献就是|right(x)|*(l-max[fa[x]])

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
int rd(){int z=,mk=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')mk=-; ch=getchar();}
while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-''; ch=getchar();}
return z*mk;
}
char a[],b[]; int n,m;
int nxt[][],fa[],mx[],sz[];
int lst=,tt=;
int cnt[],cntrk[];
ll f[];
void ist(int x){
int p=lst,np=lst=++tt;
mx[np]=mx[p]+; sz[np]=;
while(!nxt[p][x] && p) nxt[p][x]=np,p=fa[p];
if(!p) fa[np]=;
else{
int q=nxt[p][x];
if(mx[p]+==mx[q]) fa[np]=q;
else{
int nq=++tt; mx[nq]=mx[p]+;
memcpy(nxt[nq],nxt[q],sizeof(nxt[q]));
fa[nq]=fa[q],fa[q]=fa[np]=nq;
while(nxt[p][x]==q) nxt[p][x]=nq,p=fa[p];
}
}
}
void gtcntrk(){
for(int i=;i<=tt;++i) ++cnt[mx[i]];
for(int i=;i<=n;++i) cnt[i]+=cnt[i-];
for(int i=tt;i;--i) cntrk[cnt[mx[i]]--]=i;
}
void gtf(){
for(int i=tt;i;--i) sz[fa[cntrk[i]]]+=sz[cntrk[i]];
for(int i=;i<=tt;++i)
f[cntrk[i]]=f[fa[cntrk[i]]]+(ll)sz[cntrk[i]]*(mx[cntrk[i]]-mx[fa[cntrk[i]]]);
}
int main(){//freopen("ddd.in","r",stdin);
scanf("%s%s",a+,b+); n=strlen(a+),m=strlen(b+);
for(int i=;i<=n;++i) ist(a[i]-'a');
gtcntrk(),gtf();
ll bwl=; int l=,tmp=,x;
for(int i=;i<=m;++i){
x=b[i]-'a';
if(nxt[tmp][x]) tmp=nxt[tmp][x],++l;
else{
while(!nxt[tmp][x] && tmp) tmp=fa[tmp];
if(!tmp) tmp=,l=;
else l=mx[tmp]+,tmp=nxt[tmp][x];
}
if(tmp!=) bwl+=f[fa[tmp]]+(ll)sz[tmp]*(l-mx[fa[tmp]]);
}
cout<<bwl<<endl;
return ;
}