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
|
maniAC:
2014-05-14 15:04:50
DP (prefix[:i]) + Z-Function => O(n^2) get AC. |
|
Pratik kumar:
2014-03-28 17:25:05
My soln got ac in subst1 but getting wa here any trick??? |
|
innovolt:
2014-03-12 04:18:17
nice 1 ...learnt a new Data Structure..thanx SPOJ |
|
AvmnuSng:
2014-02-06 20:22:15
@swati gupta : beautiful indentation, opened the code but couldn't dare to read it. |
|
swati gupta:
2014-02-06 19:16:37
using suffix array+lcp...using radix sort instead of sort()
|
|
TYAGI:
2014-02-05 23:43:50
easy one ... jst read suffix array...geeks for geeks and algorithmist
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2013-10-20 12:41:27
Hash -> Wrong Answer
|
|
aar:
2013-08-28 12:53:04
Suffix Array with O(n * logn *logn) is accepted... |
|
co_simple:
2013-05-27 10:38:25
@XxX_Stu The problem not show the chars only with 'A'-'Z'. |
|
XxX_Stu:
2013-05-08 05:37:13
Also can use Suffix Automaton to accepted.
|
| 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 |
RSS