DISUBSTR - Distinct Substrings

Given a string, we need to find the total number of its distinct substrings.


T- number of test cases. T<=20;
Each test case consists of one string, whose length is <= 1000


For each test case output one number saying the number of distinct substrings.


Sample Input:

Sample Output:

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
Raghavendran Ramachandran: 2012-10-03 09:40:32

Can the string contain characters other than A-Za-z ?

Arun Lakshman: 2012-08-30 13:59:09


Dunno: 2012-08-15 21:57:46

welll, O(N^2) works since constraint is pretty small.

陈迪: 2012-05-26 09:42:39

suffix arr && height arr

fox_pro: 2012-05-04 06:51:40

can hash work?

谢天成: 2012-03-11 08:57:07

Suffix array too

nilaysahu: 2012-02-26 12:46:54

Last edit: 2012-02-26 12:47:23
mahmoud: 2011-08-18 05:00:12

substrings must be consecutive or not ?

Ðộc cô cầu bại: 2011-08-06 17:51:27

trie or dynamic programming can accept. I used dynamic programming to accept this problem.

Last edit: 2011-08-06 17:55:52
sandeep aggrawal: 2011-07-21 12:18:33

does the string only contain characters???

Added by:Prasanna
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource: ByteCode '06