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
kshubham02: 2016-05-26 17:28:28

Suffix array :D

pamyjeela: 2016-05-20 19:50:17

Better go for suffix array

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

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?

Edit: No need of memset .I did a silly mistake

Last edit: 2015-12-04 18:46:56
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.159s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL 6 VB.net
Resource: ByteCode '06