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.


hide comments
surayans tiwari(http://bit.ly/1EPzcpv): 2014-12-22 11:22:16

used set vector and with just 30 lines of code got it accepted

numerix: 2014-11-15 06:18:04

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
Varun Gambhir: 2014-09-04 08:12:10

Suffix Array :)

KevinMercer: 2014-08-14 07:52:38

He's wrong!There're sth far from 'A'~'Z'!

Enterprise: 2014-08-14 07:48:59

I think strings have chars besides capital letters, for I kept getting wa until I expand letter array to all chars.

maniAC: 2014-05-14 15:04:50

DP (prefix[:i]) + Z-Function => O(n^2) get AC.

Pratik kumar: 2014-03-28 17:25:05

My soln got ac in subst1 but getting wa here any trick???

innovolt: 2014-03-12 04:18:17

nice 1 ...learnt a new Data Structure..thanx SPOJ

AvmnuSng: 2014-02-06 20:22:15

@swati gupta : beautiful indentation, opened the code but couldn't dare to read it.

swati gupta: 2014-02-06 19:16:37

using suffix array+lcp...using radix sort instead of sort()
getting WA
please help: http://ideone.com/UynWET

Last edit: 2014-02-21 22:53:36

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