how to print longest common subsequence?
algorithm, c++
Solution
Typical approach with dp when you want to recover the optimal solution - add a second array of exactly the same size as the one where you memoize and store in it the 'path' you decided to take. In this case by the 'path' you decided to take I mean the branch leading to the optimal solution.
Looking at the way you implement LCS you have three options for `lcs(x, y)`:
- Its optimal result is achieved when you do `1+lcs(x+1,y+1);` i.e. you include element `x` from `a` and element `y` from b.
- You don't use element `x` from `a`. This happens if you get `dp[x][y]=max(lcs(x+1,y),lcs(x,y+1));` and in fact `lcs(x+1, y)` is the greater of the two values.
- You don't use element `y` from `b`. This happens if you get `dp[x][y]=max(lcs(x+1,y),lcs(x,y+1));` and in fact `lcs(x, y+1)` is the greater of the two values.
The two lowest bullets mean you will have to split this max statement to two ifs.
Now store which of the three choices you choose for each pair `(x,y)` and reconstructing the optimal solution should be pretty straight forward.
Problem
i am learning about lcs and implemented it..but can't find the way to print the longest common subsequence..how to print it?? my lcs code ``` #include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; int dp[1005][1005]; char a[1005],b[1005]; int lcs(int x,int y) { if(x==strlen(a)||y==strlen(b)) return 0; if(dp[x][y]!=-1) return dp[x][y]; else if(a[x]==b[y]) dp[x][y]=1+lcs(x+1,y+1); else dp[x][y]=max(lcs(x+1,y),lcs(x,y+1)); return dp[x][y]; } int main() { while(gets(a)&&gets(b)) { memset(dp,-1,sizeof(dp)); int ret=lcs(0,0); printf("%d\n",ret); } } ```