#include #include #include #include #include #define ll long long int #define M 6 using namespace std; inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;} int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1}; int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1}; const int inf=0x3f3f3f3f; const ll mod=1e9+7; int dp[107][107]; int mark[107][107]; //0表示为公共字母 1表示i-1没有贡献 -1表示j-1没有贡献 string s,t; void output(int i,int j){ //打印路径 // cout< if(i==0||j==0){ if(i==0) for(int k=0;k) cout<<t[k]; else for(int k=0;k) cout<<s[k]; return ; } if(mark[i][j]==0){ output(i-1,j-1); cout<1]; }else if(mark[i][j]==-1){ output(i-1,j); cout<1]; }else{ output(i,j-1); cout<1]; } } int main(){ ios::sync_with_stdio(false); while(cin>>s>>t){ memset(dp,0,sizeof(dp)); memset(mark,0,sizeof(mark)); int len1,len2; len1=s.length(); len2=t.length(); for(int i=1;i<=len1;i++) for(int j=1;j<=len2;j++){ if(s[i-1]==t[j-1]){ dp[i][j]=dp[i-1][j-1]+1; mark[i][j]=0; }else if(dp[i][j-1]>dp[i-1][j]){ dp[i][j]=dp[i][j-1]; mark[i][j]=1; }else{ dp[i][j]=dp[i-1][j]; mark[i][j]=-1; } } output(len1,len2); cout<<endl; } return 0; }
京公网安备 11010802041100号