Amidrunk's blog

Any help will appreciated !
By Amidrunk, 11 years ago, In English

I was solving this Problem , which is basically a LCS problem, where we have to find the length of LCS between given string and its reverse to compute the solution for it.

Problem what I am facing:

I am able to write an O(n^2) algorithm for it, but it is a TLE for the given constraint for the above mentioned problem. I dont know how to optimise it, before posting here, I tried searching an efficient implementation/algo for LCS , and I got this and this. But I am still not able to get through both or there is some other way of solving this problem ?

Tags dp, spoj, lcs
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There is another solution using dynamic programming: dp[start_pos][length]

if(s[i]==s[i+j-1])
	dp[i][j]=dp[i+1][j-2];
else
	dp[i][j]=min(dp[i][j-1],dp[i-1][j-1]);

You can use both of the solutions but you should allocate only dp[3][5001] memory. You can do this because you need only (i-1)th and (i-2)th rows of dp array to calculate i-th row.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you sparik1997:

    sorry, but I didn't get your this soln, can you explain the working of this dp approach.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      i think there is a bug in the solution above. using n^2/2 memory (n = 5000) there is another solution D(L, R) — answer for substring s[L...R]. but this solution can be implemented using only O(n) memory because we need only two last diagonals of matrix D to calculate next one.

      → Reply