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
|
|
n3gativ3:
2015-06-18 09:49:37
Z array-0.10 sec
|
|
Rishab Banerjee:
2015-06-13 18:57:39
those are using O(n*log(n)*log(n))
|
|
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 |