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
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

sultania23: 2017-06-01 09:03:58

compilation error in c++ 4.3 passed in cpp 14

sultania23: 2017-06-01 09:03:18

char other than alphabet exist !!! Be careful..

datbeohbbh: 2017-05-31 12:50:33

suffix automata

anikatahsin: 2017-05-28 01:21:41

This is my ac code -> http://paste.ubuntu.com/24684371/
But when i used below condition I got RE
if(str[i]>='a' && str[i]<='z') id = str[i] - 'a';
else if(str[i]>='A' && str[i]<='Z') id = str[i] - 'A' + 26;
But when I used
if(str[i]>='a' && str[i]<='z') id = str[i] - 'a';
else id = str[i] - 'A' + 26; it got ac .
Can anyone please explain the reason ?

s_jindal00: 2017-05-21 21:20:57

Warning : There are TC present where non alphabetical chars are given in string. Dont subtract 'A' to get rank instead use the ascii value itself

anurag_tangri: 2017-04-18 23:19:38

my first using suffix array :) AC IN ONE GO :D


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