Description

Given a string, we need to find the total number of its distinct substrings.

Input

T- number of test cases. T<=20;
Each test case consists of one string, whose length is <= 1000

Output

For each test case output one number saying the number of distinct substrings.

Example

Sample Input:
2
CCCCC
ABABA

Sample Output:
5
9

Explanation for the testcase with string ABABA: 
len=1 : A,B
len=2 : AB,BA
len=3 : ABA,BAB
len=4 : ABAB,BABA
len=5 : ABABA

Thus, total number of distinct substrings is 9.

【题意】给定一个字符串，求不相同的字串的个数。

【解题方法】每一个子串一定是某个后缀的前缀，那么问题便等价于求所有后缀之间的不相同的前缀个数。我们按sa的顺序来考虑，当加入sa[k]的时候，sa[k]这个后缀的长度为n-sa[k]，那么便有n-sa[k]个前缀，但是由heigh数组可知sa[k]与sa[k-1]有height[k]个前缀是相同的，所以要除去，最终的答案便是sigma(n-sa[k]+height[k])。

【代码君】

//
//Created by just_sort 2016/10/16
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 22222;
int sa[maxn];//SA??????S?n???????????????
             //????????????SA?
int t1[maxn],t2[maxn],c[maxn];//?SA???????????????
int Rank[maxn],height[maxn];
//?????????s?????s[0]?s[n-1],???n,??????m,
//?s[n-1]????s[i]???0?r[n-1]=0
//??????????sa???
void build_sa(int s[],int n,int m)
{
    int i,j,p,*x=t1,*y=t2;
    //??????????s??????????????
    for(i=0;i<m;i++)c[i]=0;
    for(i=0;i<n;i++)c[x[i]=s[i]]++;
    for(i=1;i<m;i++)c[i]+=c[i-1];
    for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
    for(j=1;j<=n;j<<=1)
    {
        p=0;
        //????sa?????????
        for(i=n-j;i<n;i++)y[p++]=i;//???j????????????
        for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
        //????y?????????????????
        //?????????
        for(i=0;i<m;i++)c[i]=0;
        for(i=0;i<n;i++)c[x[y[i]]]++;
        for(i=1;i<m;i++)c[i]+=c[i-1];
        for(i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
        //??sa?x??????x??
        swap(x,y);
        p=1;x[sa[0]]=0;
        for(i=1;i<n;i++)
            x[sa[i]]=y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+j]==y[sa[i]+j]?p-1:p++;
        if(p>=n)break;
        m=p;//??????????
    }
}
void getHeight(int s[],int n)
{
    int i,j,k=0;
    for(i=0;i<=n;i++)Rank[sa[i]]=i;
    for(i=0;i<n;i++)
    {
        if(k)k--;
        j=sa[Rank[i]-1];
        while(s[i+k]==s[j+k])k++;
        height[Rank[i]]=k;
    }
}

int s[maxn];
char str[maxn];

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%s", str);
        int n = strlen(str);
        for(int i = 0; i < n; i++) s[i] = str[i];
        s[n] = 0;
        build_sa(s, n +1 , 128);
        getHeight(s, n);
        int ans = 0;
        for(int i = 1; i <= n; i++){
            ans = ans + n - sa[i]  - height[i];
        }
        printf("%d\n", ans);
    }
    return 0;
}