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.


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

hide comments
2023-01-21 23:22:10
Trie/surrix tree / hashing
2022-01-19 12:04:58
This can be solved using Trie Tree, with effeciently implementation of reseting data :D
2021-02-05 13:19:47 Bo MA
It seems full ASCII character set is required. Got WA if using A-Z only.
2020-09-24 23:22:37
FFS @pradeep_7 - 4600+ AC users, and you think we need to see your pathetic code? get real
2020-09-24 19:46:15
Suffix trie
1.Dont use array in structure use map (to pass memory and tle)
2.every node we have distinct so count each and every node that we created on trie
code Link(A.C): <-- snip -->

Last edit: 2020-09-25 06:16:03
2020-01-28 23:49:09
there is only upper alphabet,, just you have to write trie in format of trie[m][26];;
2019-11-18 07:40:50
why nCr(s.size()+1,2) - sum of LCp won't accept for this problem
2019-11-07 22:27:05
Any ascii characters other than whitespaces......(trie or suffix array will pass...)
2019-04-29 16:23:51 Vinay Saini
Suffix Tree (Ukkonen's Algorithm) Accepted.

Last edit: 2019-04-29 16:24:20
2018-12-01 17:45:25
Trie of suffixes for an easy AC
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.