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
谢天成:
2012-03-11 08:57:07
Suffix array too |
|
mahmoud:
2011-08-18 05:00:12
substrings must be consecutive or not ? |
|
Ðộc cô cầu bại:
2011-08-06 17:51:27
trie or dynamic programming can accept. I used dynamic programming to accept this problem. Last edit: 2011-08-06 17:55:52 |
|
sandeep aggrawal:
2011-07-21 12:18:33
does the string only contain characters???
|
|
Zheli Zhou:
2010-07-20 01:20:55
suffix array |
|
fake:
2010-05-09 02:00:49
Is it ues KMP? |
|
Iqram Mahmud:
2010-04-04 15:57:04
Precisely, it is within 32 and 126 in ascii values. |
|
Rajesh V:
2009-06-12 08:02:53
Any ASCII characters other than whitespaces. |
|
Dima Kravtsov:
2009-06-07 17:09:56
What characters does the string contain? |
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 |