Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<sstream>
- #include<string>
- #include<cstdlib>
- #include<vector>
- #include<map>
- #include<queue>
- #include<stack>
- #include<cmath>
- #include<cctype>
- #include<set>
- #include<bitset>
- #include<algorithm>
- #include<list>
- #include<stdio.h>
- #include<string.h>
- #include<stdlib.h>
- #include<math.h>
- #include<ctype.h>
- using namespace std;
- typedef long long int ll;
- #define PI 3.14159265358979323846
- struct node{
- int x,y;
- }res[110][110];
- string s1,s2,ss1,ss2;
- bool vis[110][110];
- string ans;
- int dp[110][110],mm[110][110];
- void cal(int i,int j)
- {
- if(dp[i][j]==0)
- return ;
- if(vis[i][j]==1)
- {
- ans+=s1[i];
- cout<<ans<<endl;
- }
- cal(res[i][j].x,res[i][j].y);
- }
- int main()
- {
- //freopen("0in.txt","r",stdin);
- //freopen("0out.txt","w",stdout);
- int tcase,t,i,j,cnt,end,l1,l2;
- scanf("%d",&tcase);
- for(t=1;t<=tcase;t++)
- {
- cin>>ss1>>ss2;
- s1="";
- s2="";
- char ch='z'+1;
- s1 = "#"+ss1;
- s2 = "#"+ss2;
- l1 = ss1.size();
- l2 = ss2.size();
- memset(dp,0,sizeof dp);
- for(i=0;i<=l1;i++)
- mm[i][0]='z'+1;
- for(i=0;i<=l2;i++)
- mm[0][i]='z'+1;
- for(i=1;i<=l1;i++)
- {
- for(j=1;j<=l2;j++)
- {
- vis[i][j] = 0;
- res[i][j].x=0;
- res[i][j].y = 0;
- if(s1[i]==s2[j])
- {
- dp[i][j] = dp[i-1][j-1] + 1;
- }
- else
- {
- dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
- }
- }
- }
- for(i=0;i<=l2;i++)
- cout<<s2[i]<<" ";
- cout<<endl;
- for(i=1;i<=l1;i++)
- {
- cout<<s1[i]<<" ";
- for(j=1;j<=l2;j++)
- {
- if(s1[i]==s2[j])
- {
- res[i][j].x = i-1;
- res[i][j].y = j-1;
- vis[i][j] = 1;
- mm[i][j]=s1[i]-96;
- cout<<"A"<<" ";
- }
- else if(dp[i-1][j]==dp[i][j-1])
- {
- if(mm[i][j-1]<mm[i-1][j])
- {
- res[i][j].x = i;
- res[i][j].y = j-1;
- mm[i][j]=mm[i][j-1];
- cout<<"L"<<" ";
- }
- else
- {
- res[i][j].x = i-1;
- res[i][j].y = j;
- mm[i][j]=mm[i-1][j];
- cout<<"U"<<" ";
- }
- }
- else
- {
- if(dp[i-1][j]>dp[i][j-1])
- {
- res[i][j].x = i-1;
- res[i][j].y = j;
- mm[i][j]=mm[i-1][j];
- cout<<"U"<<" ";
- }
- else{
- res[i][j].x = i;
- res[i][j].y = j-1;
- mm[i][j]=mm[i][j-1];
- cout<<"L"<<" ";
- }
- }
- }
- cout<<endl<<endl;
- }
- ans = "";
- //cal(l1,l2);
- i=l1;
- j=l2;
- while(dp[i][j]!=0)
- {
- if(vis[i][j]==1)
- {
- ans=s1[i]+ans;
- }
- i=res[i][j].x;j=res[i][j].y;
- }
- cout<<ans<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement