BZOJ3238:[AHOI2013]差异(SAM)

Description

Input

一行，一个字符串S

Output

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

Sample Input

cacao

Sample Output

HINT

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

Solution

后缀自动机的fa指针反向以后可以形成一个树结构，称作Parent树
一个节点的father是他的最长后缀，那么很显然任意两个子串的最长公共后缀位于它们Parent树对应节点的lca处
为了利用这个性质，可以把串反过来建立SAM，问题转化成对这个串的所有前缀求最长公共后缀
要注意只有np节点才能代表前缀
一对对枚举前缀求lcs显然是不可能的，可以考虑对于每个子串，它是多少对前缀的最长公共后缀
也就是对于每个节点，求它是多少对前缀节点的LCA
然后DFS一下就好了

Code

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #define N (1000000+1000)
 5 using namespace std;
 6 
 7 struct Edge{int to,next;}edge[N<<1];
 8 long long ans;
 9 int head[N],num_edge;
10 char s[N];
11 
12 void add(int u,int v)
13 {
14     edge[++num_edge].to=v;
15     edge[num_edge].next=head[u];
16     head[u]=num_edge;
17 }
18 
19 struct SAM
20 {
21     int fa[N],son[N][28],right[N],step[N],od[N],wt[N],size[N];
22     int p,q,np,nq,last,cnt;
23     SAM(){last=++cnt;}
24     
25     void Insert(int x)
26     {
27         p=last; last=np=++cnt; step[np]=step[p]+1; size[np]=1;
28         while (p && !son[p][x]) son[p][x]=np,p=fa[p];
29         if (!p) fa[np]=1;
30         else
31         {
32             q=son[p][x];
33             if (step[p]+1==step[q]) fa[np]=q;
34             else
35             {
36                 nq=++cnt; step[nq]=step[p]+1;
37                 memcpy(son[nq],son[q],sizeof(son[q]));
38                 fa[nq]=fa[q]; fa[q]=fa[np]=nq;
39                 while (son[p][x]==q) son[p][x]=nq,p=fa[p];
40             }
41         }
42     }
43      void Dfs(int x,int fa)
44      {
45          long long sum=0,is_one=(size[x]==1);
46          for (int i=head[x]; i; i=edge[i].next)
47              if (edge[i].to!=fa)
48              {
49                  Dfs(edge[i].to,x);
50                  size[x]+=size[edge[i].to];
51                  ans-=2*sum*size[edge[i].to]*step[x];
52                  sum+=size[edge[i].to];
53              }
54          if (is_one) ans-=2ll*(size[x]-1)*step[x];
55      }
56 }SAM;
57 
58 int main()
59 {
60     scanf("%s",s);
61     long long len=strlen(s);
62     ans=(len-1)*len/2*(len+1);
63     for (int i=len-1; i>=0; --i)
64         SAM.Insert(s[i]-'a');
65     for (int i=2; i<=SAM.cnt; ++i)
66         add(i,SAM.fa[i]),add(SAM.fa[i],i);
67     SAM.Dfs(1,-1);
68     printf("%lld",ans);
69 }