akashtomar19's blog

improve memoization of lowest common substring
By akashtomar19, history, 5 years ago, In English

I was solving lowest common substring problem using memoization ,But i was unable to reduce the size of dp table,can this be done using 2d array ,here I am using 3d array.

int dp[100][100][100];
int lcsubstr(int i, int j, int s) {
    if(dp[i][j][s]!=-1)return dp[i][j][s];
	int cnt = 0;
	if (i == 0 || j == 0)return cnt;
	if (a[i - 1] == b[j - 1]) {
		cnt = max(s+1,lcsubstr(i - 1, j - 1, s + 1));
	}

	cnt = max(cnt, max(lcsubstr(i - 1, j, 0), lcsubstr(i, j - 1, 0)));
	return dp[i][j][s]=cnt;
}
  • Vote: I like it
  • -9
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You don't need to memorize the string for every state but only the choice that you have taken, if $$$lcsubstr(i - 1, j) > lcsubstr(i, j - 1)$$$ then it's better to skip the ith character of a, otherwise it's better to skip the jth character of b. So you can memorize your choices and then backtrack the final string.

#include<bits/stdc++.h>
using namespace std;
int const MAXN=1100;
string a, b;
int memo[MAXN][MAXN], choice[MAXN][MAXN];
int dp(int i, int j){
	if(memo[i][j]!=-1) 
		return memo[i][j];
	if(i==a.length() || j==b.length())
		return memo[i][j]=0;
	if(a[i]==b[j]){
		choice[i][j]=1; // take the character
		return memo[i][j]=1+dp(i+1,j+1);
	}
	int try_a=dp(i+1,j), try_b=dp(i,j+1);
	if(try_a>try_b){
		choice[i][j]=2; // skip the ith character
		return memo[i][j]=try_a;
	}
	else{
		choice[i][j]=3; //   skip the jth character
		return memo[i][j]=try_b;
	}
}
string backtrack(){
	string res="";
	int i=0, j=0;
	while(i<a.length() && j<b.length()){
		if(choice[i][j]==1){
			res+=a[i];
			i++, j++;
		}
		else if(choice[i][j]==2)	i++;
		else j++;
	}
	return res;
}
int main(){
	cin>>a>>b;
	for(int i=0;i<a.length();i++)
		for(int j=0;j<b.length();j++)
			memo[i][j]=-1;
	cout<<dp(0,0)<<endl;
	cout<<backtrack();
}

If you want to save memory you can make choice[][] as boolean, and manually check if a[i]==b[j] and use true for skipping the ith character of a, false for skipping the jth character of b.

→ Reply