LCS dynamic programming using one dimensional array

Question

I am trying to do dynamic programming for finding length of LCS. I have used two dimensional array for that. But for a large string it gives runtime error due to memory overflow. Please tell me How should I do it in one dimensional array to avoid memory constrains.

#include<bits/stdc++.h>
 #include<string.h> 
 using namespace std;
int max(int a, int b);
int lcs( string X, string Y, int m, int n )
{
   int L[m+1][n+1];
   int i, j;
   for (i=0; i<=m; i++)
   {
     for (j=0; j<=n; j++)
     {
       if (i == 0 || j == 0)
         L[i][j] = 0;

       else if (X[i-1] == Y[j-1])
         L[i][j] = L[i-1][j-1] + 1;

       else
         L[i][j] = max(L[i-1][j], L[i][j-1]);
     }
   }

   return L[m][n];
}

int max(int a, int b)
{
    return (a > b)? a : b;
}

int main()
{
  string X;
  string Y;
  cin>>X>>Y;
  int m = X.size();
  int n = Y.size();

  printf("Length of LCS is %d\n", lcs( X, Y, m, n ) );

  return 0;
}

[OT] int L[m+1][n+1]; use variable length array extension, prefer to use std::vector. — Jarod42
– Jarod42, Commented Mar 17, 2016 at 12:37
vector is also giving runtime error for input string around 500k — Abhishek Dudhal
– Abhishek Dudhal, Commented Mar 17, 2016 at 12:39
Tricky; you probably need to adapt Hirshberg’s algorithm to solve this. It’s feasible, but definitely much more complex than the simple LCS algorithm (EDIT: Ah, you’re only interested in the length, not the actual subsequence; that’s much easier, see Sergei’s answer). Unrelatedly, you definitely need to use vector instead of variable-length arrays; also, switch on compiler warnings (-Wall -Wextra on GCC and clang) and make your compiler pedantic (-pedantic on GCC and clang). — Konrad Rudolph
– Konrad Rudolph, Commented Mar 17, 2016 at 12:41

Sergei Lebedev · Accepted Answer · 2016-03-17 12:41:12Z

5

Note that the recursion in lcs only uses the last two rows of the L matrix. Thus you can easily rewrite your solution to use O(N) memory.

Here's a good article on the subject.

answered Mar 17, 2016 at 12:41

Sergei Lebedev

2,67920 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

jonezq · Accepted Answer · 2016-03-17 12:40:37Z

0

two dimensional array is fiction anyway, it's still one dimensional array, so calculate indexes on your own, ie: so your array int L[(n+1)(m+1)] and index of L[i][j] = L[i(n+1)+j]

answered Mar 17, 2016 at 12:40

jonezq

3541 silver badge5 bronze badges

Collectives™ on Stack Overflow

LCS dynamic programming using one dimensional array

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related