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;
}
This makes your DP run in Θ(n4) time. Try reusing some computation in the string comparisons.
Thank you so much! :)