技术笔记：SCU4484

The Graver Robbers' Chronicles

Description

One day, Kylin Zhang and Wu Xie are trapped in a graveyard. They find an ancient piece of parchment with a cipher string.

After discussion and analysis, they find the password is the total number of the cipher string's distinct substrings.

Although Kylin Zhang is powerful and always help his friends get rid of danger, this time he is helpless beacause

he is not good at math and programming.

As a smart Acmer, can you help them solve this problem so that they can escape from this horrible graveyard.

Input

The first line is an integer T stands for the number of test cases.

Then T test case follow.

For each test case there is one string.

Constraints:

T is no bigger than 30.

The length of string is no bigger than 50000.

Every string only contains lowercase letters.

Output

For each test case, output the answer in a single line. one number saying the number of distinct substrings.

Sample Input

2

aaaaa

cacac

Sample Output

5

9

Hint

For test case 2, the distinct substrings of 'cacac' are as follows:

len = 1 : c , a

len = 2 : ca , ac

len = 3 : cac , aca

len = 4 : caca , acac

len = 5 : cacac

Thus, total number of distinct substrings is 9.

分析：字符串的处理问题，查重的时候使用后缀数组就可以了。

算出总的子串 len(len+1)/2

再减去重复的 Height(i)

即可

套用了一下 大大的后缀数组模板，地址：

代码如下：

#include

#include

#include

#define LL long long

#define ULL unsigned long long

using namespace std;

const int MAXN=100010;

//以下为倍增算法求后缀数组

int wa【MAXN】,wb【MAXN】,wv【MAXN】,Ws【MAXN】;

int cmp(int //代码效果参考：http://www.lyjsj.net.cn/wz/art_23208.html

{return r【a】==r【b】&&r【a+l】==r【b+l】;}

/< 传入参数：str,sa,len+1,ASCII_MAX+1 /

void da(const char r【】,int sa【】,int n,int m)

{

int i,j,p,x=wa,y=wb,t;

for(i=0; i

for(i=0; i

for(i=1; i

for(i=n-1; i>=0; i--) sa【--Ws【x【i】】】=i;

/cout["SA"[endl;;

for(int i=0;i<n+1;i++)cout[sa【i】[' ';/

for(j=1,p=1; p

{

for(p=0,i=n-j; i

for(i=0; i=j) y【p++】=sa【i】-j;

for(i=0; i

for(i=0; i

for(i=0; i

//代码效果参考：http://www.lyjsj.net.cn/wz/art_23206.html

for(i=n-1; i>=0; i--) sa【--Ws【wv【i】】】=y【i】;

for(t=x,x=y,y=t,p=1,x【sa【0】】=0,i=1; i

x【sa【i】】=cmp(y,sa【i-1】,sa【i】,j)?p-1:p++;

}

return;

}

int sa【MAXN】,Rank【MAXN】,height【MAXN】;

//求height数组

/< str,sa,len /

void calheight(const char r,int sa,int n)

{

int i,j,k=0;

for(i=1; i<=n; i++) Rank【sa【i】】=i;

for(i=0; i

for(k?k--:0,j=sa【Rank【i】-1】; r【i+k】==r【j+k】; k++);

// Unified

for(int i=n;i>=1;--i) ++sa【i】,Rank【i】=Rank【i-1】;

}

int main()

{

char r【MAXN】;

int m,n,t;

LL H,ans;

cint;

while(t--)

{

cinr;

n=strlen(r);

m=127;

da(r,sa,n+1,m+1);

calheight(r,sa,n);

H=n;

ans=(H+1)H/2;

for(int i=2;i<=n;i++)

{

ans-=height【i】;

}

cout[ans[endl;

}

}