Optimizing O(m n) solution for longest common subsequence challenge

Given two strings string X of length x1 and string Y of length y1, find the longest sequence of characters that appear left to right (but not necessarily in contiguous block) in both strings.


e.g. if X = ABCBDAB and Y = BDCABA, the LCS(X,Y) = {"BCBA","BDAB","BCAB"} and LCSlength is 4.

I used the standard solution for this problem, whichever is greater:

• if(X[i]=Y[j]) :1+LCS(i+1,j+1)

• if(X[i]!=Y[j]) :LCS(i,j+1)

• LCS(i+1,j)

and then I used memorization, making it a standard DP problem.

#include
#include
using namespace std;
int LCS[1024][1024];
int LCSlen(string &x,int x1,string &y,int y1){
    for(int i = 0; i = 0; i--){
    for(int j = y1 - 1; j >= 0; j--){

    LCS[i][j] = LCS[i+1][j+1];

    if(x[i] == y[j])
    LCS[i][j]++;

    if(LCS[i][j+1]>LCS[i][j])
    LCS[i][j]=LCS[i][j+1];

    if(LCS[i+1][j]>LCS[i][j])
    LCS[i][j]=LCS[i+1][j];

    }
    }
return LCS[0][0];
} 

int main()
{
string x;
string y;
cin >> x >> y;
int x1 = x.length() , y1 = y.length();
int ans = LCSlen( x, x1, y, y1);
cout << ans << endl;
return 0;
}

Running here, this solution I used in SPOJ and I got a time limit exceeded and/or runtime error.

Only 14 solutions are yet accepted. Is there a smarter trick to decrease the time complexity of this question?

The algorithm is correct, but the implementation is sort of naive; it definitely doesn't scale to 50000-long strings. Even for the 1024-long strings it is very cache-unfriendly; most likely you spend most of the time in cache misses.

The wiki article mentions that


dynamic programming approach only needs the current and previous
columns of the matrix

Modify your code to run in a linear space. That shall give you a boost.

StackExchange Code Review Q#52308, answer score: 4