[BZOJ3238][AHOI2013]差异(SAM)

3238: [Ahoi2013]差异
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 4320 Solved: 1969
[Submit][Status][Discuss]
Description

Input

一行，一个字符串S

Output

一行，一个整数，表示所求值

Sample Input

cacao

Sample Output

54

HINT

2<=N<=500000,S由小写英文字母组成

Source
[Submit][Status][Discuss]

曾经的AHOI也出过这样的好题。。

首先SA+单调栈可以做，但是看到式子第一反应就觉得和树上两点距离和很有关系，显然是后缀树上DP啊。

后缀树不会怎么办？后缀自动机的fa就构成了一棵树。

SAM性质：两个前缀的LCS等于它们在fa树上的LCA的len。

对反串建出SAM然后直接DP跑就好了。SAM数组记得开两倍。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define rep(i,l,r) for (int i=l; i<=r; i++)
 5 typedef long long ll;
 6 using namespace std;
 7 
 8 const int N=1000100;
 9 char s[N];
10 int n,m,p,lst=1,np,cnt=1,mx[N],d[N],fa[N],son[N][26],q[N],c[N];
11 ll ans,sum[N];
12 
13 void ext(int c){
14     p=lst; lst=np=++cnt; mx[np]=mx[p]+1; d[np]=1;
15     while (!son[p][c] && p) son[p][c]=np,p=fa[p];
16     if (!p) fa[np]=1;
17     else{
18         int q=son[p][c];
19         if (mx[q]==mx[p]+1) fa[np]=q;
20         else{
21             int nq=++cnt; mx[nq]=mx[p]+1;
22             memcpy(son[nq],son[q],sizeof(son[q]));
23             while (p && son[p][c]==q) son[p][c]=nq,p=fa[p];
24             fa[nq]=fa[q]; fa[q]=fa[np]=nq;
25         }
26     }
27 }
28 
29 void radix(){
30     rep(i,0,n) c[i]=0;
31     rep(i,1,cnt) c[mx[i]]++;
32     rep(i,1,n) c[i]+=c[i-1];
33     for (int i=cnt; i; i--) q[c[mx[i]]--]=i;
34 }
35 
36 int main(){
37     freopen("bzoj3238.in","r",stdin);
38     freopen("bzoj3238.out","w",stdout);
39     scanf("%s",s+1); n=strlen(s+1); reverse(s+1,s+1+n);
40     ll ans=1ll*n*(n+1)*(n-1)/2,res=0;
41     rep(i,1,n) ext(s[i]-'a'); radix();
42     for (int i=cnt; i; i--) res+=1ll*mx[fa[q[i]]]*d[fa[q[i]]]*d[q[i]],d[fa[q[i]]]+=d[q[i]];
43     printf("%lld
",ans-2*res);
44     return 0;
45 }