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.
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
Simple Suffix Array (O(n*lg^2n)) with lcp