Блог пользователя Amidrunk

Any help will appreciated !
Автор Amidrunk, 11 лет назад, По-английски

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 ?

Теги dp, spoj, lcs
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thank you sparik1997:

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

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить