Amidrunk's blog

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 ?

Full text and comments »

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