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

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

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