CODEWITHSUNDEEP
c++
user2739256
user2739256

Reputation:

longest common subsequence of bigger strings?

if the each of the strings length is greater than 60000 then i tried by using two array because i couldn't declare an array of like dp[60000][60000]..so that's why i tried like that but the time limit exceeded...how to do for the longer srings..is there any way within time like 3 or 5 sec?

#include<iostream>
#include<cstring>
#include<string.h>
#include<algorithm>
using namespace std;
const int size=50000;
int dp_x[size+1],dp_xp1[size+1];
char a[size+1],b[size+1];
int lcs()
{
    int strlena=strlen(a);
    int strlenb=strlen(b);
    for(int y=0;y<=strlenb;y++)
        dp_x[y]=0;
    for(int x=strlena-1;x>=0;x--)
    {
        memcpy(dp_xp1,dp_x,sizeof(dp_x));
        dp_x[strlenb]=0;
        for(int y=strlenb-1;y>=0;y--)
        {
            if(a[x]==b[y])
                dp_x[y]=1+dp_xp1[y+1];
            else
                dp_x[y]=max(dp_xp1[y],dp_x[y+1]);
        }
    }
    return dp_x[0];
}
int main()
{
    while(gets(a)&&gets(b))
    {
        int ret=lcs();
        cout<<ret<<endl;
    }
}

Upvotes: 0

Views: 208

Answers (1)

Fred Foo
Fred Foo

Reputation: 363517

In each iteration, you're memcpy'ing a row. That takes O(n) time per iteration, so O(n²) time in total. Replace the memcpy by a pointer swap. So, instead of working on dp_x and dp_x1 directly, use two pointers, initially:

int *current = dp_x, previous = dp_x1;

Then, inside your loop, replace the copy with a swap:

std::swap(current, previous);

Upvotes: 1

Related Questions