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.


T- number of test cases. T<=20;
Each test case consists of one string, whose length is <= 1000


For each test case output one number saying the number of distinct substrings.


Sample Input:

Sample Output:

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
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-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 Innovolt
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
2013-08-28 12:53:04 aar
Suffix Array with O(n * logn *logn) is accepted...
2013-05-27 10:38:25 co_simple
@XxX_Stu The problem not show the chars only with 'A'-'Z'.
2013-05-08 05:37:13 XxX_Stu
Also can use Suffix Automaton to accepted.
String just have chars which 'A'-'Z'.
2013-03-23 08:27:04 Jarily
newbie go past
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.