题目描述】
给定一个字符串，计算其不同的子串个数。
【输入格式】
一行一个仅包含大写字母的字符串，长度<=50000
【输出格式】
一行一个正整数，即不同的子串个数。
【样例输入】
ABABA
【样例输出】
9
题解：
显然后缀可以是一个子串，然后后缀中可能包含多个子串。
我们考虑不重复统计，容易发现 一个后缀的贡献为L-high[i]+1
因为high[i]之前的显然可以在后面的串中被统计到，所以可以避免重复
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=;
char s[N];int n,k,rk[N],sa[N],tmp[N],high[N];
bool comp(int i,int j){
if(rk[i]!=rk[j])return rk[i]<rk[j];
int ri=i+k<=n?rk[i+k]:-;
int rj=j+k<=n?rk[j+k]:-;
return ri<rj;
}
void Getsa(){
for(int i=;i<=n;i++)sa[i]=i,rk[i]=s[i];
for(k=;k<=n;k<<=){
sort(sa+,sa+n+,comp);
for(int i=;i<=n;i++)tmp[sa[i]]=tmp[sa[i-]]+comp(sa[i-],sa[i]);
for(int i=;i<=n;i++)rk[i]=tmp[i];
}
}
void Gethight(){
int j,h=;
for(int i=;i<=n;i++){
j=sa[rk[i]-];
if(h)h--;
for(;j+h<=n && i+h<=n;h++)if(s[i+h]!=s[j+h])break;
high[rk[i]-]=h;
}
}
void Getanswer(){
long long ans=;
for(int i=;i<=n;i++){
if(high[i]==n-sa[i]+)continue;
ans+=n-sa[i]+-high[i];
}
printf("%lld\n",ans);
}
int main()
{
freopen("subst1.in","r",stdin);
freopen("subst1.out","w",stdout);
scanf("%s",s+);
n=strlen(s+);
Getsa();Gethight();Getanswer();
return ;
}