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.
Did it using suffix array and lcp.... my code works fine on hackerEarth, but shows Runtime Error (NZEC) here. Can anyone please tell what's causing this error!! code:https://ideone.com/Gh9Bxg
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
If you write an O(n) algorithm of suffix array(such as "DC3" or "SA-IS") , you just need to calculate the LCP of every two suffix which rank is nearby,then you just use sigma(1~lenth(string)) minus sigma(i=1 to lenth(string))height i; the answer will be calculated. The whole algorithm will be O(n).
kmp rocks :)
"SUBST1 - New Distinct Substrings" - NOT passed in (NLOG^2N) string length large
0.00 suffix array rocks
AAA is also a possible substring of length 3