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
|
mrtsepa:
2018-10-09 18:45:19
Python 3.5 -- TL, Python 2.7 -- AC. How?? Last edit: 2018-10-09 18:45:29 |
|
sherlock11:
2018-06-19 14:38:39
suffix array->kasai's algorithm->AC:) |
|
chetan4060:
2017-12-21 17:03:30
very good question |
|
Samuel Nacache:
2017-10-12 17:28:34
Naive Suffix Array and LCP implementation leads to AC in 0.00 |
|
sultania23:
2017-06-01 09:03:58
compilation error in c++ 4.3 passed in cpp 14 |
|
|
sultania23:
2017-06-01 09:03:18
char other than alphabet exist !!! Be careful..
|
|
datbeohbbh:
2017-05-31 12:50:33
suffix automata |
|
anikatahsin:
2017-05-28 01:21:41
This is my ac code -> http://paste.ubuntu.com/24684371/
|
|
s_jindal00:
2017-05-21 21:20:57
Warning : There are TC present where non alphabetical chars are given in string. Dont subtract 'A' to get rank instead use the ascii value itself |
|
anurag_tangri:
2017-04-18 23:19:38
my first using suffix array :) AC IN ONE GO :D |
| 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