題面

BZOJ

題解

后綴數(shù)組的做法，應該不是很難想
首先看到兩個不同的串，當然是接在一起求 SA,height
那么，考慮一下暴力
在兩個串各枚舉一個后綴，他們的 lcp 就是對答案產(chǎn)生的貢獻

現(xiàn)在優(yōu)化一下，按照 SA 的順序枚舉來處理 lcp
利用一個單調(diào)棧維護一下，每次記錄一下前面有多少個的貢獻和當前答案一樣就好啦
只是有點難寫。。。

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<set> #include<map> #include<vector> #include<queue> using namespace std; #define MAX 440000 #define ll long long int n,gr[MAX]; int SA[MAX],hg[MAX],rk[MAX]; int a[MAX],t[MAX],x[MAX],y[MAX]; bool cmp(int i,int j,int k){return y[i]==y[j]&&y[i+k]==y[j+k];} void GetSA() {int m=50;for(int i=1;i<=n;++i)t[x[i]=a[i]]++;for(int i=1;i<=m;++i)t[i]+=t[i-1];for(int i=n;i>=1;--i)SA[t[x[i]]--]=i;for(int k=1;k<=n;k<<=1){int p=0;for(int i=1;i<=n;++i)y[i]=0;for(int i=n-k+1;i<=n;++i)y[++p]=i;for(int i=1;i<=n;++i)if(SA[i]>k)y[++p]=SA[i]-k;for(int i=0;i<=m;++i)t[i]=0;for(int i=1;i<=n;++i)t[x[y[i]]]++;for(int i=1;i<=m;++i)t[i]+=t[i-1];for(int i=n;i>=1;--i)SA[t[x[y[i]]]--]=y[i];swap(x,y);x[SA[1]]=p=1;for(int i=2;i<=n;++i)x[SA[i]]=cmp(SA[i],SA[i-1],k)?p:++p;if(p>=n)break;m=p;}for(int i=1;i<=n;++i)rk[SA[i]]=i;for(int i=1,j=0;i<=n;++i){if(j)--j;while(a[i+j]==a[SA[rk[i]-1]+j])++j;hg[rk[i]]=j;} } int Q1[MAX],top1,S1[MAX]; int Q2[MAX],top2,S2[MAX]; ll ans,sum1,sum2; char ch[MAX]; int main() {scanf("%s",ch+1);for(int i=1,l=strlen(ch+1);i<=l;++i)a[++n]=ch[i]-96,gr[n]=1;a[++n]=27;scanf("%s",ch+1);for(int i=1,l=strlen(ch+1);i<=l;++i)a[++n]=ch[i]-96,gr[n]=2;GetSA();for(int i=1,tot=0;i<n;++i){ans+=(gr[SA[i]]==1)?sum2:sum1;ll tmp1=0;while(top1&&Q1[top1]>=hg[i+1]){tmp1+=S1[top1];sum1-=1ll*(Q1[top1]-hg[i+1])*S1[top1];--top1;}++top1;S1[top1]=tmp1;Q1[top1]=hg[i+1];ll tmp2=0;while(top2&&Q2[top2]>=hg[i+1]){tmp2+=S2[top2];sum2-=1ll*(Q2[top2]-hg[i+1])*S2[top2];--top2;}++top2;S2[top2]=tmp2;Q2[top2]=hg[i+1];if(gr[SA[i]]==1)++S1[top1],sum1+=hg[i+1];else ++S2[top2],sum2+=hg[i+1];}printf("%lld\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的【BZOJ4566】找相同字符（后缀数组）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。