DISUBSTR - Distinct Substrings


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.


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
<snip>

Last edit: 2023-05-16 22:18:55
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 ?


Added by:Prasanna
Date:2006-01-13
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource: ByteCode '06