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.


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

mahmudul12: 2017-03-31 14:12:27

The string will contain any character

ayush5148: 2017-03-08 19:48:45

The strings will be in uppercase letters only...

nilabja16180: 2017-03-07 13:53:33

Lots of Learning then Finally AC!

vunnamtej: 2017-01-18 07:42:01

vector of suffixes of string and sorting 0.01s


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