链接：https://ac.nowcoder.com/acm/contest/558/A
来源：牛客网
A.串串
小猫在研究字符串。
小猫在研究字串。
给定一个长度为N的字符串S，问所有它的子串Sl…r(1≤l≤r≤N)，去重后有多少种。
输入描述:
一行一个字符串S。
输出描述:
一行一个整数，表示答案。
备注:
1≤N≤10
5
，字符都是小写字母
后缀自动机模板题，因为数据太大，极限可能为1e10,要开long long
不会后缀自动机，贴个板子。
代码:
//A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn =1e5+;
char s[maxn];
ll len;
ll T; struct SAM{
ll last,cnt,nxt[maxn*][],fa[maxn*],l[maxn*];
ll ans;
void init(){
last = cnt=;
memset(nxt[],,sizeof nxt[]);
fa[]=;ans=;l[]=;
}
ll inline newnode(){
++cnt;
memset(nxt[cnt],,sizeof nxt[cnt]);
fa[cnt]=l[cnt]=;
return cnt;
}
void add(ll c){
ll p = last;
ll np = newnode();
last = np;
l[np] = l[p]+;
while (p&&!nxt[p][c]){
nxt[p][c]=np;
p = fa[p];
}
if (!p){
fa[np]=;
}else{
ll q = nxt[p][c];
if (l[q]==l[p]+){
fa[np] = q;
}else{
ll nq = newnode();
memcpy(nxt[nq],nxt[q],sizeof nxt[q]);
fa[nq] = fa[q];
l[nq] = l[p]+;
fa[np]=fa[q]=nq;
while (nxt[p][c]==q){
nxt[p][c]=nq;
p=fa[p];
}
}
}
// cout<<fa[last]<<endl;
ans+=l[last]-l[fa[last]];
}
void query(){
ll l,r;
l=,r=len;
init();
for (ll i=l;i<=r;i++){
// cout<<s[i]<<" ";
add(s[i]-'a');
}
printf("%lld\n",ans);
}
}sam; int main(){
scanf("%s",s+);
len=strlen(s+);
// cout<<len<<endl;
sam.query();
return ;
}