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
davidgalehouse:
20161022 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: 20161022 08:31:29 

Jinal :
20160907 20:18:50
Did it using suffix array and lcp.... my code works fine on hackerEarth, but shows Runtime Error (NZEC) here. Can anyone please tell what's causing this error!! code:https://ideone.com/Gh9Bxg 

hardik_iitr:
20160802 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:
20160731 06:22:15
If you use suffix array, you can solve for O(n). So I was able to get 0.00s.


deerishi:
20160713 01:59:16
Awesome Problem!! Learnt a lot. 

janvijay1997:
20160712 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:
20160628 14:28:13
If you write an O(n) algorithm of suffix array(such as "DC3" or "SAIS") , 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:
20160317 14:56:34
kmp rocks :) 

Debashish Deka:
20160124 15:22:42
"SUBST1  New Distinct Substrings"  NOT passed in (NLOG^2N) string length large


Sumit Vohra:
20160118 19:21:40
0.00 suffix array rocks

Added by:  Prasanna 
Date:  20060113 
Time limit:  0.159s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL 6 VB.net 
Resource:  ByteCode '06 