DISUBSTR - 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 <= 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.


Added by:Prasanna
Date:2006-01-13
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource: ByteCode '06

hide comments
2015-05-04 08:32:02 Crazyxx
Suffix_Automaton XD
2015-02-14 06:17:04 the_imp
what should be the answer for "AbABa"..... i'm using suffix array and lcs getting wa

Last edit: 2015-02-14 06:50:44
2015-01-28 12:19:51 Rajat (1307086)
Got a new definition of sub string:
"prefix of all suffixes of a string is sub string."
2015-01-25 06:35:44 Kishlay Raj
learnt alot
2014-12-24 21:18:01 gamer496
finally after 3 days of understanding suffix array and lcp and numerous wrong answers
2014-12-22 11:22:16 surayans tiwari(http://bit.ly/1EPzcpv)
used set vector and with just 30 lines of code got it accepted
2014-11-15 06:18:04 numerix
Another problem that switched from Pyramid to Cube within the last 12 hours. Time limit seems to be adjusted "automatically", but should be less strict for slower languages.
The rejudge process is either incomplete or doesn't work correctly as there are still AC Python submissions that use psyco (not supported on Cube), while others (e.g. mine ...) are no longer valid.

--ans(Francky)--> I suspect too that rejudge is incomplete... I saw that when PRIME1 switched. Edit : but it seems there's still Py2-psyco submissions for PRIME1 ; can you confirm or not ? There shouldn't be no more such AC one, right ?

Reply of numerix: Yes, there are AC psyco submissions left in PRIME1 and also some other problems.
According to time limit here: There is an actual AC Python submission with PyPy, so it is possible to get AC with Python if algorithm is well designed.

Last edit: 2014-11-16 16:32:47
2014-09-04 08:12:10 Varun Gambhir
Suffix Array :)
2014-08-14 07:52:38 KevinMercer
He's wrong!There're sth far from 'A'~'Z'!
2014-08-14 07:48:59 Enterprise
I think strings have chars besides capital letters, for I kept getting wa until I expand letter array to all chars.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.