?

?

3238: [Ahoi2013]差異

Time Limit:?20 Sec??Memory Limit:?512 MB
Submit:?4840??Solved:?2298
[Submit][Status][Discuss]

Description

Input

一行，一個字符串S

Output

?

一行，一個整數，表示所求值

Sample Input

cacao

Sample Output

54

HINT

?

2<=N<=500000,S由小寫英文字母組成

?

Source

[Submit][Status][Discuss]

?

?

題解：這題曾用后綴數組做過，因為那時候來不及也學不會SAM，就對著GXZlegend的博客學了一遍打了一遍，然后就忘了，那就SAM來寫一遍吧。其實這也算是個論文題，2015國家集訓隊論文中有提到，雖然其實很簡單。就是把原串反過來建SAM可以得到后綴樹，然后兩個后綴的最長公共前綴就變成了lca的深度（其實我是不懂后綴樹的，但是yy一下就起碼能意會是這樣），于是計算每個點的貢獻就好了，這，，就是很“熟悉”的樹形dp呀，直接這個節點的節點數C(n,2)就是了，然后每個點的深度就是max-min+1，即sr[a].len-sr[sr[a].ff].len。前面那部分暴力算，每個點都出現了n-1次。

#include<bits/stdc++.h> #define pb push_back #define mp make_pair #define ll long long using namespace std; const int maxn=1e6+100; char s[maxn]; struct str {int son[26];int ff,len; }sr[maxn]; int cnt=1,last=1; int siz[maxn],c[maxn],a[maxn]; void extend(int c) {int p=last,np=++cnt;last=np;sr[np].len=sr[p].len+1;while(p&&!sr[p].son[c])sr[p].son[c]=np,p=sr[p].ff;if(!p)sr[np].ff=1;else{int q=sr[p].son[c];if(sr[p].len+1==sr[q].len)sr[np].ff=q;else{int nq=++cnt;sr[nq]=sr[q];sr[nq].len=sr[p].len+1;sr[q].ff=sr[np].ff=nq;while(p&&sr[p].son[c]==q)sr[p].son[c]=nq,p=sr[p].ff;}}siz[np]=1; } int main() {int t;scanf("%s",s+1);int len=strlen(s+1);//memset(sr,0,sizeof(sr));cnt=1;last=1;for(int i=len;i;i--)extend(s[i]-'a');for(int i=1;i<=cnt;i++)c[sr[i].len]++;for(int i=1;i<=cnt;i++)c[i]+=c[i-1];for(int i=1;i<=cnt;i++)a[c[sr[i].len]--]=i;for(int i=cnt;i;i--)siz[sr[a[i]].ff]+=siz[a[i]];ll ans=0;for(int i=1;i<=len;i++)ans+=1ll*i*(len-1);for(int i=1;i<=cnt;i++)ans-=1ll*siz[i]*(siz[i]-1)*(sr[i].len-sr[sr[i].ff].len);cout<<ans<<"\n"; }

　　后綴數組就先只貼代碼了，用了單調棧。。EC前的沒有腦子的代碼。

#include<bits/stdc++.h> #define ll long long #define pb push_back #define ill inline #define mp make_pair #define db double #define eps 1e-9 #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=5e5+7; const double pi=acos(-1); inline ll read() {ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } int rankk[maxn],sa[maxn],x[maxn],y[maxn],c[maxn],height[maxn]; int sta[maxn],l[maxn],r[maxn]; char S[maxn]; int ps[maxn]; int n,m,top; void da() {m=27;int i,j,p;for(i=0;i<n;i++)c[x[i]=ps[i]]++;for(i=1;i<m;i++)c[i]+=c[i-1];for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;for( p=1,j=1;p<n;j<<=1,m=p){for(p=0,i=n-j;i<n;i++)y[p++]=i;for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;for(i=0;i<m;i++)c[i]=0;for(i=0;i<n;i++)c[x[y[i]]]++;for(i=1;i<m;i++)c[i]+=c[i-1];for(i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];for(swap(x,y),p=i=1,x[sa[0]]=0;i<n;i++){if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j])x[sa[i]]=p-1;else x[sa[i]]=p++;}}for(i=1;i<n;i++)rankk[sa[i]]=i;for(p=i=0;i<n-1;height[rankk[i++]]=p)for(p?p--:p,j=sa[rankk[i]-1];ps[i+p]==ps[j+p];p++); } int main() {scanf("%s",S);n=strlen(S);int i;for(i=0;i<n;i++)ps[i]=S[i]-'a'+1;n++;da();n--;sta[0]=1;for(i=2;i<=n;i++){while(top&&height[sta[top]]>=height[i])top--;l[i]=i-sta[top],sta[++top]=i;}top=0,sta[0]=n+1;for(i=n;i>=2;i--){while(top&&height[sta[top]]>height[i])top--;r[i]=sta[top]-i,sta[++top]=i;}ll ans=0;for(i=2;i<=n;i++)ans+=2ll*r[i]*l[i]*height[i];cout<<1ll*n*(n+1)*(n-1)/2-ans<<"\n"; }

　　

轉載于:https://www.cnblogs.com/intwentieth/p/10415616.html

總結

以上是生活随笔為你收集整理的BZOJ3238: [Ahoi2013]差异的全部內容，希望文章能夠幫你解決所遇到的問題。

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