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
|
mahmudul12:
2017-03-31 14:12:27
The string will contain any character |
|
ayush5148:
2017-03-08 19:48:45
The strings will be in uppercase letters only...
|
|
nilabja16180:
2017-03-07 13:53:33
Lots of Learning then Finally AC! |
|
vunnamtej:
2017-01-18 07:42:01
vector of suffixes of string and sorting 0.01s |
|
kiwi1995:
2016-12-13 10:22:14
suffix tree :D |
|
Fabian Conejo:
2016-10-29 20:46:52
Try this case:
|
|
davidgalehouse:
2016-10-22 08:30:59
I was kind of intimidated by this problem, because I thought the standard implementations were pretty complicated and I didn't want to learn all the nitty gritty details. Understanding how the LCP array and suffix array work together was enough, then I just constructed them ad hoc. The runtime was good enough at 0.02s, and I still got a lot out of it. I'll wait for harder problems to do the better big O constructions. Last edit: 2016-10-22 08:31:29 |
|
hardik_iitr:
2016-08-02 09:19:25
Learnt a whole lot about string algos through this problem. Probably the toughest one on strings I ever solved. Dont assume the characters to be alphabetical, dont subtract 'A' in deciding the rank. I got many WA's because of that. |
|
square1001:
2016-07-31 06:22:15
If you use suffix array, you can solve for O(n). So I was able to get 0.00s.
|
|
deerishi:
2016-07-13 01:59:16
Awesome Problem!! Learnt a lot. |
| 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