DISUBSTR - Distinct Substrings

no tags 

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

kiwi1995: 2016-12-13 10:22:14

suffix tree :D

Fabian Conejo: 2016-10-29 20:46:52

Try this case:

davidgalehouse: 2016-10-22 08:30:59

I was kind of intimidated by this problem, because I thought the standard implementations were pretty complicated and I didn't want to learn all the nitty gritty details. Understanding how the LCP array and suffix array work together was enough, then I just constructed them ad hoc. The runtime was good enough at 0.02s, and I still got a lot out of it. I'll wait for harder problems to do the better big O constructions.

Last edit: 2016-10-22 08:31:29
hardik_iitr: 2016-08-02 09:19:25

Learnt a whole lot about string algos through this problem. Probably the toughest one on strings I ever solved. Dont assume the characters to be alphabetical, dont subtract 'A' in deciding the rank. I got many WA's because of that.

square1001: 2016-07-31 06:22:15

If you use suffix array, you can solve for O(n). So I was able to get 0.00s.
I made a similar problem "Substrings" (Japanese) in AtCoder.
This problem says:
"Print the sum of length of the all distinct substring in the string S?" and (length of S)<100000.

Last edit: 2016-07-31 06:29:15
deerishi: 2016-07-13 01:59:16

Awesome Problem!! Learnt a lot.

janvijay1997: 2016-07-12 17:04:11

My solution using suffix arrays giving wrong answer : https://ideone.com/pd9BQB .Please help ! Same code worked well for NEW DISTINCT SUBSTRINGS :O

Added by:Prasanna
Time limit:0.159s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource: ByteCode '06