lax_99's blog

By lax_99, history, 6 years ago, In English

Problem Link : SAMER08D I wrote a recursive solution and also memoized it for the problem which is a modified version of the classical LCS. I tried a lot of test cases from SPOJ Toolkit and also the sample test cases and my program gave the correct output. Not sure why my solution gives TLE. Can anyone help me out figure out the mistake?

#include <bits/stdc++.h>
using namespace std;

string a, b;
int cache[1010][1010];
int k;

int dpSol(int i, int j)
{
    if(i == a.size() || j == b.size())
        return 0;
    if(cache[i][j] != -1)
        return cache[i][j];
    int ans = 0;
    for(int l = k; ; l++)
    {
        if(i + l - 1 < a.size() && j + l - 1 < b.size())
        {
            if(a.substr(i, l) == b.substr(j, l))
                ans = max(dpSol(i + l, j + l) + l, ans);
            else
                ans = max({dpSol(i + 1, j), dpSol(i, j + 1), ans});
        }
        else
            break;
    }
    return cache[i][j] = ans;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    while(cin >> k && k)
    {
        cin >> a;
        cin >> b;
        memset(cache, -1, sizeof(cache));
        cout << dpSol(0, 0) << endl;
    }

    return 0;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
            if(a.substr(i, l) == b.substr(j, l))

This makes your DP run in Θ(n4) time. Try reusing some computation in the string comparisons.