题意：
给定一个字符串,求不相同的子串的个数
分析：
每个子串一定是某个后缀的前缀,那么原问题等价于求所有后缀之间的不相同 的 前 缀 的 个 数 。
如 果 所 有 的 后 缀 按 照 suffix(sa[1]), suffix(sa[2]),suffix(sa[3]), ...... ,suffix(sa[n])的顺序计算,
不难发现,对于每一次新加进来的 后缀 suffix(sa[k]), 它将产生 n-sa[k] 个新 的前缀。
但 是其中有height[k]个是和前面的字符串的前缀是相同的。
所以 suffix(sa[k])将“贡献”出 n-sa[k]- height[k]个不同的子串。
累加后便是原问题的答案。这个做法的时间复杂度为 O(n)。
// File Name: 694.cpp
// Author: Zlbing
// Created Time: 2013年09月06日 星期五 13时34分31秒 #include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define LL long long
#define REP(i,r,n) for(int i=r;i<=n;i++)
#define RREP(i,n,r) for(int i=n;i>=r;i--)
//rank从0开始
//sa从1开始,因为最后一个字符(最小的)排在第0位
//height从2开始,因为表示的是sa[i-1]和sa[i]
const int MAXN=;
int rank[MAXN],sa[MAXN],X[MAXN],Y[MAXN],height[MAXN];
char s[MAXN];
int buc[MAXN];
void calheight(int n) {
int i , j , k = ;
for(i = ; i <= n ; i++) rank[sa[i]] = i;
for(i = ; i < n ; height[rank[i++]] = k)
for(k?k--: , j = sa[rank[i]-] ; s[i+k] == s[j+k] ; k++);
}
bool cmp(int *r,int a,int b,int l) {
return (r[a] == r[b] && r[a+l] == r[b+l]);
}
void suffix(int n,int m = ) {
int i , l , p , *x = X , *y = Y;
for(i = ; i < m ; i ++) buc[i] = ;
for(i = ; i < n ; i ++) buc[ x[i] = s[i] ] ++;
for(i = ; i < m ; i ++) buc[i] += buc[i-];
for(i = n - ; i >= ; i --) sa[ --buc[ x[i] ]] = i;
for(l = ,p = ; p < n ; m = p , l *= ) {
p = ;
for(i = n-l ; i < n ; i ++) y[p++] = i;
for(i = ; i < n ; i ++) if(sa[i] >= l) y[p++] = sa[i] - l;
for(i = ; i < m ; i ++) buc[i] = ;
for(i = ; i < n ; i ++) buc[ x[y[i]] ] ++;
for(i = ; i < m ; i ++) buc[i] += buc[i-];
for(i = n - ; i >= ; i --) sa[ --buc[ x[y[i]] ] ] = y[i];
for(swap(x,y) , x[sa[]] = , i = , p = ; i < n ; i ++)
x[ sa[i] ] = cmp(y,sa[i-],sa[i],l) ? p- : p++;
}
calheight(n-);//后缀数组关键是求出height,所以求sa的时候顺便把rank和height求出来
}
int solve(int n)
{
int ans=;
ans+=n-sa[];
for(int i=;i<=n;i++)
{
ans+=n-sa[i]-height[i];
}
return ans;
}
int main() {
int cas;
scanf("%d",&cas);
while(cas--)
{
scanf("%s",s);
int n=strlen(s);
s[n]=;
suffix(n+);
int ans=solve(n);
printf("%d\n",ans);
}
return ;
}