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
varun_pandey: 2020-01-28 23:49:09

there is only upper alphabet,, just you have to write trie in format of trie[m][26];;

maruf_1604089: 2019-11-18 07:40:50

why nCr(s.size()+1,2) - sum of LCp won't accept for this problem

limon_88: 2019-11-07 22:27:05

Any ascii characters other than whitespaces......(trie or suffix array will pass...)

Vinay Saini: 2019-04-29 16:23:51

Suffix Tree (Ukkonen's Algorithm) Accepted.

Last edit: 2019-04-29 16:24:20
phoemur: 2018-12-01 17:45:25

Trie of suffixes for an easy AC

mrtsepa: 2018-10-09 18:45:19

Python 3.5 -- TL, Python 2.7 -- AC. How??

Last edit: 2018-10-09 18:45:29
sherlock11: 2018-06-19 14:38:39

suffix array->kasai's algorithm->AC:)

edwardfrog: 2018-03-16 09:42:21

Last edit: 2018-03-16 10:46:16
chetan4060: 2017-12-21 17:03:30

very good question

Samuel Nacache: 2017-10-12 17:28:34

Naive Suffix Array and LCP implementation leads to AC in 0.00


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