DISUBSTR - Distinct Substrings

no tags 

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

hide comments
ojasva_jain: 2015-07-29 22:47:22

Will AA and aa be considered different strings?

Raghav Aggiwal Again: 2015-07-25 13:33:25

Suffix Array !

xxbloodysantaxx: 2015-07-17 09:49:34

@n3gativ3 - My Z array solution takes 0.02 seconds to run!!

Rydel Dcosta: 2015-06-30 20:26:53

my code got AC for this but WA for SUBST1 :/ can somebody help me ??whats wrong in my code

n3gativ3: 2015-06-18 09:49:37

Z array-0.10 sec
KMP failure function-0.1 sec
Suffix Array-0,00 sec :)

Rishab Banerjee: 2015-06-13 18:57:39

those are using O(n*log(n)*log(n))
try http://www.spoj.com/problems/SUBST1/
i got AC here but getting TLE in SUBST1

Sherlock: 2015-06-13 09:34:46

can anybody help me out ?? getting runtime error??

arp_ee: 2015-06-10 14:24:54

first prob on suffix array !!

Shubham Bansal: 2015-05-22 18:04:00

phew..!! learnt alot from dis!!

i_am_looser: 2015-05-07 09:21:08

Can this question be solved using Trie ?