题意
求一个字符串的不同子串数量
思路
该字符串的所有后缀子串的前缀子串即为改字符串的所有子串数量。总的子串数量=len*(len+1)/2,那么重复的子串如何求呢？即为height数组的总和，对排名相邻两个的后缀，他们的重复前缀的前缀都是重复的,raokou~
如排名为1,2的后缀子串
1 a a a a b
2 a a a b
最长公共前缀的长度是3
该公共前缀的前缀a || a a || a a a在1 2 中重复出现，故减去
#pragma GCC optimize(2)
#include<bits/stdc++.h>using namespace std;typedef long long ll;
typedef unsigned long ul;
typedef unsigned long long ull;
#define pi acos(-1.0)
#define e exp(1.0)
#define pb push_back
#define mk make_pair
#define fir first
#define sec second
#define scf scanf
#define prf printf
typedef pair<ll,ll> pa;
//const ll INF=0x3f3f3f3f3f3f3f3f;
const ll maxn=2e4+7;
ll T,N,K,rank[maxn],sa[maxn],height[maxn],tmp[maxn];
string s;
bool cmp(ll i,ll j){if(rank[i]!=rank[j])return rank[i]<rank[j];ll r1=i+K<=N?rank[i+K]:-1;ll r2=j+K<=N?rank[j+K]:-1;return r1<r2;
}
void do_sa(){ll i,j;for(i=0;i<=N;i++){sa[i]=i;rank[sa[i]]=(i!=N?s[i]:-1);}for(K=1;K<=N;K<<=1){sort(sa,sa+1+N,cmp);tmp[sa[0]]=0;for(i=1;i<=N;i++){tmp[sa[i]]=tmp[sa[i-1]]+(cmp(sa[i-1],sa[i])?1:0);}for(i=0;i<=N;i++)rank[i]=tmp[i];}return ;
}
void get_height(){ll i,j,k=0;for(i=0;i<N;i++){if(k)k--;elsek=0;j=sa[rank[i]-1];while(s[i+k]==s[j+k])k++;height[rank[i]]=k;}return ;
}
int main()
{
// freopen(".../.txt","w",stdout);
// freopen(".../.txt","r",stdin);ios::sync_with_stdio(false);cin>>T;ll i,j,k;while(T--){cin>>s;N=s.length();do_sa();get_height();ll res=N*(N+1)/2;for(i=1;i<=N;i++)
// cout<<height[i]<<' ';res-=height[i];cout<<res<<endl;}return 0;
}