I am trying solving http://www.spoj.com/problems/LCS0/. The normal dp solution will certainly not work. I also tried for the space efficient solution in which we keep track of two rows only. But as the solution still has O(M*N) complexity where M and N are the lengths (<=50000), it gives TLE. Can anyone please tell a better approach. I searched and got to know the similarity between this problem and the Edit distance problem also, but couldn’t understand. Can someone please give it a start!!
Try using suffix array or suffix tree.
Link:-http://sugionline.com/blog/?p=289
Hope this helps.Happy Coding 