DISUBSTR - Distinct Substrings

no tags 

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
Jinal : 2016-09-07 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: 2016-08-02 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: 2016-07-31 06:22:15

If you use suffix array, you can solve for O(n). So I was able to get 0.00s.
I made a similar problem "Substrings" (Japanese) in AtCoder.
This problem says:
"Print the sum of length of the all distinct substring in the string S?" and (length of S)<100000.
https://s8pc-2.contest.atcoder.jp/tasks/s8pc_2_e

Last edit: 2016-07-31 06:29:15
deerishi: 2016-07-13 01:59:16

Awesome Problem!! Learnt a lot.

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
"DISUBSTR - Distinct Substrings" - passed in (NLOG^2N) small string length

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


Added by:Prasanna
Date:2006-01-13
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