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