Sphere Online Judge



SPOJ Problem Set (classical)

694. Distinct Substrings

Problem code: DISUBSTR

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.159s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All except: NODEJS PERL 6 SCM chicken VB.net
Resource: ByteCode '06

hide comments
2015-01-28 12:19:51 Arvind Kejriwal
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 Jasdeep Singh
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.
2014-05-14 15:04:50 maniAC
DP (prefix[:i]) + Z-Function => O(n^2) get AC.
2014-03-28 17:25:05 Pratik kumar
My soln got ac in subst1 but getting wa here any trick???
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.