| Submit | All submissions | Best solutions | Back to list |
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.
| 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 |
hide comments
|
||||||||||||
|
2023-01-21 23:22:10
Trie/surrix tree / hashing |
||||||||||||
|
2022-01-19 12:04:58
This can be solved using Trie Tree, with effeciently implementation of reseting data :D |
||||||||||||
|
2021-02-05 13:19:47 Bo MA
It seems full ASCII character set is required. Got WA if using A-Z only. |
||||||||||||
|
2020-09-24 23:22:37
FFS @pradeep_7 - 4600+ AC users, and you think we need to see your pathetic code? get real |
||||||||||||
|
2020-09-24 19:46:15
Suffix trie 1.Dont use array in structure use map (to pass memory and tle) 2.every node we have distinct so count each and every node that we created on trie code Link(A.C): <-- snip --> Last edit: 2020-09-25 06:16:03 |
||||||||||||
|
2020-01-28 23:49:09
there is only upper alphabet,, just you have to write trie in format of trie[m][26];; |
||||||||||||
|
2019-11-18 07:40:50
why nCr(s.size()+1,2) - sum of LCp won't accept for this problem |
||||||||||||
|
2019-11-07 22:27:05
Any ascii characters other than whitespaces......(trie or suffix array will pass...) |
||||||||||||
|
2019-04-29 16:23:51 Vinay Saini
Suffix Tree (Ukkonen's Algorithm) Accepted. Last edit: 2019-04-29 16:24:20 |
||||||||||||
|
2018-12-01 17:45:25
Trie of suffixes for an easy AC |
||||||||||||
RSS