'Longest common subsequence using Dynamic programming
I am trying to implement the code of the longest common subsequence(LCS) using Dynamic Programming. I have chosen two strings "abcdef" and "abcdfe".The answer should be 6 but I am getting 5.I have checked the code and algorithm several times. Below is the code.
#include <bits/stdc++.h>
using namespace std;
int max(int a,int b){
return a>b?a:b;
}
void c(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
}
int main() {
c();
string str1="abcdef",str2="abcdfe";
int n=str1.length(),m=str2.length();
int t[n+1][m+1];
for(int i=0;i<n+1;i++){
for(int j=0;j<m+1;j++){
t[i][j]=0;
}
}
for(int i=1;i<n+1;i++){
for(int j=1;j<m+1;j++){
if(str1[i-1]==str2[j-1]){
t[i][j]=1+t[i-1][j-1];
}
else{
t[i][j]=max(t[i-1][j],t[i][j-1]);
}
}
}
for(int i=0;i<n+1;i++){
for(int j=0;j<m+1;j++){
cout<<t[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
