I was reading http://www.stanford.edu/class/cs97si/suffix-array.pdf. In problem 6, I am unable to figure out n^2 DP solution. I tried to think about it, but I was not able to reduce it less than simple O(n^3), where state is (i,j,k) -> ans : i is position in S1, j in S2, k in S3.
I feel like that I can optimize it shuffling the state parameters, something like (i,j) -> (k, ans). But I am not able to correctly write the recurrence.
Please help me in finding the O(n*n) solution, If you could tell about the recurrence of above DP states, then I would be very thankful for that.
Can you also suggest similar task, where I could test my implementation ??
Well, I think there's a mistyping in this book ,maybe the writer meant O(N^3) because the writer said:
If the strings were smaller in length, the problem could have been easily solved using dinamic programmingbut O(N^2) may pass , so I think he/she meant O(N^3)
You can try this problem .Problem Link
this problem is similar to your problem.
bt you've to register first in the site. You can also try some other suffix array problem, as the problems are categorized according to algorithm.
Thanks man, I will solve it with suffix array :)