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
Resource: ByteCode '06

hide comments
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???
2014-03-12 04:18:17 N@vlOk
nice 1 ...learnt a new Data Structure..thanx SPOJ
2014-02-06 20:22:15 Abhimanyu Singh
@swati gupta : beautiful indentation, opened the code but couldn't dare to read it.
2014-02-06 19:16:37 swati gupta
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
2014-02-05 23:43:50 TYAGI
easy one ... jst read suffix array...geeks for geeks and algorithmist


Last edit: 2014-02-05 23:44:18
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.