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

Question

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<iostream>
#include<string>
using namespace std;
int LCS[1024][1024];
int LCSlen(string &x,int x1,string &y,int y1){
 for(int i = 0; i <= x1; i++)
 LCS[i][y1]=0;
 for(int j=0;j<=y1;j++)
 LCS[x1][j]=0;
 for(int i = x1 - 1; 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?

• syb0rg: I don't have the time to write a full out answer, but you should use memset(LCS, 0, sizeof(LCS[0][0]) * x1 * y1); instead of those 2 for loops at the beginning in order to zero out your matrix.
• swapedoc: but that doesn't optimize it much .
• vnp: SPOJ mentions that a string may have 50000 letters. Your code handles no more that 1024. That definitely accounts for a runtime error.

Answer 1

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.

Answer 2

Although I still didn't get an AC because of time limit exceeded ,I was however able to implement the linear space algorithm.In case anyone wants to see, here is the c++ implementation of the Hirschbirg algorithm.

#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
using namespace std;
int* compute_help_table(const string & A,const string & B);
string lcs(const string & A, const string & B);
string simple_solution(const string & A, const string & B);
int main(void) {
 string A,B;
 cin>>A>>B;
 cout << lcs(A, B).size() << endl;
 return 0;
}
string lcs(const string &A, const string &B) {
 int m = A.size();
 int n = B.size();
 if (m == 0 || n == 0) {
 return "";
 }
 else if(m == 1) {
 return simple_solution(A, B);
 }
 else if(n == 1) {
 return simple_solution(B, A);
 }
 else {
 int i = m / 2;
 string Asubstr = A.substr(i, m - i);
 //reverse(Asubstr.begin(), Asubstr.end());
 string Brev = B;
 reverse(Brev.begin(), Brev.end());
 int* L1 = compute_help_table(A.substr(0, i), B);
 int* L2 = compute_help_table(Asubstr, Brev);
 int k;
 int M = -1;
 for(int j = 0; j <= n; j++) {
 if(M < L1[j] + L2[n-j]) {
 M = L1[j] + L2[n-j];
 k = j;
 }
 }
 delete [] L1;
 delete [] L2;
 return lcs(A.substr(0, i), B.substr(0, k)) + lcs(A.substr(i, m - i), B.substr(k, n - k));
 }
}
int* compute_help_table(const string &A, const string &B) {
 int m = A.size();
 int n = B.size();
 int* first = new int[n+1];
 int* second = new int[n+1];
 for(int i = 0; i <= n; i++) {
 second[i] = 0;
 }
 for(int i = 0; i < m; i++) {
 for(int k = 0; k <= n; k++) {
 first[k] = second[k]; 
 }
 for(int j = 0; j < n; j++) {
 if(j == 0) {
 if (A[i] == B[j])
 second[1] = 1;
 }
 else {
 if(A[i] == B[j]) {
 second[j+1] = first[j] + 1;
 }
 else {
 second[j+1] = max(second[j], first[j+1]);
 }
 }
 }
 }
 delete [] first;
 return second;
}
string simple_solution(const string & A, const string & B) {
 int i = 0;
 for(; i < B.size(); i++) {
 if(B.at(i) == A.at(0))
 return A;
 }
 return "";
}