AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=4566

【題解】

我們還是先把A串建成SAM，然后讓B串在SAM上跑

因為相同子串數=不同長度的子串數*出現次數

所以每個結點對答案的貢獻就是Right[x]*(len-Min(x)+1)

我們知道SAM的一個性質：Min(x)-1=Max(parent(x))

所以貢獻就是Right[x]*(len-Max(parent(x)))

求出Right集即可。

因為如果當前結點被訪問過一次，那么它的祖先一定被訪問過了（Right(x)是Right(parent(x))的真子集）

所以我們要按照拓撲序更新parent節點

每個parent節點的貢獻是Right[x]*(Max[x]-Max(parent(x)))

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; #define FILE "read" #define MAXN 400010 #define up(i,j,n) for(int i=j;i<=n;++i) #define dn(i,j,n) for(int i=j;i>=n;--i) #define cmax(a,b) a=max(a,b) #define cmin(a,b) a=min(a,b) int n,len,cnt(1),now(1),mx[MAXN],Right[MAXN],f[MAXN],c[MAXN],id[MAXN],vis[MAXN],g[MAXN],son[MAXN][27]; ll ans; char ch[MAXN]; void insert(int x){int p=now,np=++cnt;mx[np]=mx[now]+1; now=np; Right[np]=1;while(!son[p][x]&&p) son[p][x]=np,p=f[p];if(!p) f[np]=1;else{int q=son[p][x];if(mx[q]==mx[p]+1) f[np]=q;else{int nq=++cnt;mx[nq]=mx[p]+1;memcpy(son[nq],son[q],sizeof(son[q]));f[nq]=f[q]; f[q]=f[np]=nq;while(son[p][x]==q) son[p][x]=nq,p=f[p];}} } void topsort(){up(i,1,cnt) c[mx[i]]++;up(i,1,n) c[i]+=c[i-1];up(i,1,cnt) id[c[mx[i]]--]=i;dn(i,cnt,1) Right[f[id[i]]]+=Right[id[i]]; } int main(){freopen(FILE".in","r",stdin);freopen(FILE".out","w",stdout);scanf("%s",ch+1); n=strlen(ch+1);up(i,1,n) insert(ch[i]-'a');topsort();scanf("%s",ch+1); n=strlen(ch+1); now=1;up(i,1,n){while(!son[now][ch[i]-'a']&&now) now=f[now],len=mx[now];if(!son[now][ch[i]-'a']) {now=1;len=0;}else now=son[now][ch[i]-'a'],len++;vis[now]++; ans+=(ll)Right[now]*(len-mx[f[now]]);}dn(i,cnt,2) g[f[id[i]]]+=g[id[i]]+vis[id[i]];up(i,2,cnt) ans+=(ll)g[i]*Right[i]*(mx[i]-mx[f[i]]);printf("%lld\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的【bzoj4566】找相同字符 后缀自动机的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。