SUBST1 - New Distinct Substrings


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 <= 50000

Output

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

Example

Input:
2
CCCCC
ABABA

Output:
5
9

hide comments
Daniel: 2012-08-21 09:51:36

Suffix Array can do it!It's the same as the problem 694.Suffix Array can solve it within only 0.4s.

bean: 2012-06-15 04:02:04

Why can I get AC in this problem but not in problem 694?

Last edit: 2012-06-15 04:02:54
Gaurav Menghani: 2011-08-03 13:41:26

I had to replace strlen by pointer arithmetic, and sort by qsort to get AC. Sigh :-(

Jitendra: 2011-07-28 08:19:53

qsort is faster than stl sort. stl sort gives tle while qsort soln accepted :)

Thomas Dybdahl Ahle: 2011-07-09 22:55:14

I would say "" is a substring of any string, but I notice it isn't counted in the examples. Or maybe its the string itself that isn't counted as a substring?

Leopoldo Taravilse: 2010-06-02 12:51:09

Do the strings contain the ' ' char?

lccycc: 2010-02-25 15:45:52

length is <= 50000
I know.. but it's no the problem
I have open all arrays to 1100000

The problem is: it need long long for n and the output

Last edit: 2010-02-25 16:06:39
[Rampage] Blue.Mary: 2010-02-25 15:40:53

Read the problem statement (especially the input section) CAREFULLY

lccycc: 2010-02-25 15:25:32

What's the difference between this problem and 694?

Ray: 2009-11-30 13:05:48

The time limit should be loosen. For Python(Psyco), it is nearly impossible to AC by Suffix Array.


Added by:Hoang Hong Quan
Date:2006-01-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:Base on a problem in ByteCode06