Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define MAX 1000
- char str1[MAX],str2[MAX];
- int lenA,lenB;
- int dp[MAX][MAX];
- bool visited[MAX][MAX];
- int LCS(int i,int j)
- {
- if(str1[i]=='\0' || str2[j]=='\0') return 0;
- if(visited[i][j])return dp[i][j];
- int ans=0;
- if(str1[i]==str2[j]) ans=1+LCS(i+1,j+1);
- else
- {
- int val1=LCS(i+1,j);
- int val2=LCS(i,j+1);
- ans=max(val1,val2);
- }
- visited[i][j]=1;
- dp[i][j]=ans;
- return dp[i][j];
- }
- string ans;
- void printLCS(int i,int j)
- {
- if(str1[i]=='\0' or str2[j]=='\0'){
- cout<<ans<<endl;
- return;
- }
- if(str1[i]==str2[j]){
- ans+=str1[i];
- printLCS(i+1,j+1);
- }
- else
- {
- if(dp[i+1][j]>dp[i][j+1]) printLCS(i+1,j);
- else printLCS(i,j+1);
- }
- }
- int main() {
- scanf("%s%s",str1,str2);
- lenA=strlen(str1);
- lenB=strlen(str2);
- LCS(0,0);
- printLCS(0,0);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement