PraveenDhinwa's blog

Help in Finding a DP solution to a problem.
By PraveenDhinwa, 11 years ago, In English

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

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 programming

but O(N^2) may pass , so I think he/she meant O(N^3)

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply