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
|
janvijay1997:
2016-07-12 17:04:11
My solution using suffix arrays giving wrong answer : https://ideone.com/pd9BQB .Please help ! Same code worked well for NEW DISTINCT SUBSTRINGS :O |
|
haogram:
2016-06-28 14:28:13
If you write an O(n) algorithm of suffix array(such as "DC3" or "SA-IS") , you just need to calculate the LCP of every two suffix which rank is nearby,then you just use sigma(1~lenth(string)) minus sigma(i=1 to lenth(string))height i; the answer will be calculated. The whole algorithm will be O(n). |
|
cosmopoliton:
2016-03-17 14:56:34
kmp rocks :) |
|
Debashish Deka:
2016-01-24 15:22:42
"SUBST1 - New Distinct Substrings" - NOT passed in (NLOG^2N) string length large
|
|
Sumit Vohra:
2016-01-18 19:21:40
0.00 suffix array rocks
|
|
koushik24:
2016-01-07 17:27:01
AAA is also a possible substring of length 3
|
|
dhumketu:
2016-01-06 12:31:11
Simple Suffix Array (O(n*lg^2n)) with lcp
|
|
utkarsh5:
2015-12-30 09:30:21
Anybody getting TLE in Java?
|
|
Chirag Agarwal:
2015-12-04 18:35:58
Some people suggest to use memset but where should I use it?
|
|
Ankit:
2015-08-10 17:17:27
costed so many wrong ans, used memset then finally 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