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.


Added by:Prasanna
Date:2006-01-13
Time limit:0.159s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All except: NODEJS PERL 6 SCM chicken VB.net
Resource: ByteCode '06

hide comments
Shubham Bansal: 2015-05-22 18:04:00

phew..!! learnt alot from dis!!

i_am_looser: 2015-05-07 09:21:08

Can this question be solved using Trie ?

Crazyxx: 2015-05-04 08:32:02

Suffix_Automaton XD

mehrunesartem: 2015-04-15 17:07:16

Last edit: 2015-04-15 17:13:32
L: 2015-02-14 18:46:13

Last edit: 2015-03-10 20:10:01
the_imp: 2015-02-14 06:17:04

what should be the answer for "AbABa"..... i'm using suffix array and lcs getting wa

Last edit: 2015-02-14 06:50:44
Rajat (1307086): 2015-01-28 12:19:51

Got a new definition of sub string:
"prefix of all suffixes of a string is sub string."

Kishlay Raj: 2015-01-25 06:35:44

learnt alot

gamer496: 2014-12-24 21:18:01

finally after 3 days of understanding suffix array and lcp and numerous wrong answers

surayans tiwari(http://bit.ly/1EPzcpv): 2014-12-22 11:22:16

used set vector and with just 30 lines of code got it accepted