牛客网 桂林电子科技大学第三届ACM程序设计竞赛 A.串串-后...

盛夏的果实

链接：https://ac.nowcoder.com/acm/contest/558/A
来源：牛客网


A.串串
小猫在研究字符串。
小猫在研究字串。
给定一个长度为N的字符串S，问所有它的子串Sl…r(1≤l≤r≤N)，去重后有多少种。

输入描述:

一行一个字符串S。

输出描述:

一行一个整数，表示答案。

示例1

输入
复制

ababa

输出
复制9

备注: 1≤N≤10

，字符都是小写字母

后缀自动机模板题，因为数据太大，极限可能为1e10,要开long long
不会后缀自动机，贴个板子。
代码:

1 //A
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 typedef long long ll;
 5 const ll maxn =1e5+100;
 6 char s[maxn];
 7 ll len;
 8 ll T;
 9 
10 struct SAM{
11   ll last,cnt,nxt[maxn*2][26],fa[maxn*2],l[maxn*2];
12   ll ans;
13   void init(){
14     last = cnt=1;
15     memset(nxt[1],0,sizeof nxt[1]);
16     fa[1]=0;ans=0;l[1]=0;
17   }
18   ll inline newnode(){
19     ++cnt;
20     memset(nxt[cnt],0,sizeof nxt[cnt]);
21     fa[cnt]=l[cnt]=0;
22     return cnt;
23   }
24   void add(ll c){
25     ll p = last;
26     ll np = newnode();
27     last = np;
28     l[np] = l[p]+1;
29     while (p&&!nxt[p][c]){
30       nxt[p][c]=np;
31       p = fa[p];
32     }
33     if (!p){
34       fa[np]=1;
35     }else{
36       ll q = nxt[p][c];
37       if (l[q]==l[p]+1){
38         fa[np] = q;
39       }else{
40         ll nq = newnode();
41         memcpy(nxt[nq],nxt[q],sizeof nxt[q]);
42         fa[nq] = fa[q];
43         l[nq] = l[p]+1;
44         fa[np]=fa[q]=nq;
45         while (nxt[p][c]==q){
46           nxt[p][c]=nq;
47           p=fa[p];
48         }
49       }
50     }
51 //    cout<<fa[last]<<endl;
52     ans+=l[last]-l[fa[last]];
53   }
54   void query(){
55     ll l,r;
56     l=1,r=len;
57     init();
58     for (ll i=l;i<=r;i++){
59 //      cout<<s[i]<<" ";
60       add(s[i]-'a');
61     }
62     printf("%lld\n",ans);
63   }
64 }sam;
65 
66 int main(){
67   scanf("%s",s+1);
68   len=strlen(s+1);
69 //  cout<<len<<endl;
70   sam.query();
71   return 0;
72 }