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.
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.
The strings will be in uppercase letters only...
Lots of Learning then Finally AC!
vector of suffixes of string and sorting 0.01s
suffix tree :D
Try this case:
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
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.
If you use suffix array, you can solve for O(n). So I was able to get 0.00s.
Awesome Problem!! Learnt a lot.
My solution using suffix arrays giving wrong answer : https://ideone.com/pd9BQB .Please help ! Same code worked well for NEW DISTINCT SUBSTRINGS :O