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:1s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All except: NODEJS PERL 6
Resource: ByteCode '06

hide comments
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 ITSMYLIFE
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
2013-10-20 12:41:27 (Tjandra Satria Gunawan)(曾毅昆)
Hash -> Wrong Answer
Tree -> Time Limit Exceeded
Goto forum, modify someone code -> Accepted :-P
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.