SPOJ.com - Problem DISUBSTR

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.

Submit solution!

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

2018-10-09 18:45:19
Python 3.5 -- TL, Python 2.7 -- AC. How??

Last edit: 2018-10-09 18:45:29

2018-06-19 14:38:39
suffix array->kasai's algorithm->AC:)

2017-12-21 17:03:30
very good question

2017-10-12 17:28:34 Samuel Nacache
Naive Suffix Array and LCP implementation leads to AC in 0.00

2017-06-01 09:03:58
compilation error in c++ 4.3 passed in cpp 14

2017-06-01 09:03:18
char other than alphabet exist !!! Be careful..

2017-05-31 12:50:33
suffix automata

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 ?

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

2017-04-18 23:19:38
my first using suffix array :) AC IN ONE GO :D