Pagini recente » Cod sursa (job #2004027) | Cod sursa (job #2410949) | Cod sursa (job #1992826) | Cod sursa (job #1645355) | Cod sursa (job #2947321)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
#define cin fin
#define cout fout
void lcs(char* X, char* Y, int m, int n)
{
int L[m+1][n+1];
for(int i=0;i<=m;i++)
{
for(int j=0;j<=n;j++)
{
if(i==0||j==0)
L[i][j]=0;
else if(X[i-1]==Y[j-1])
L[i][j]=L[i-1][j-1] +1;
else L[i][j]=max(L[i-1][j],L[i][j-1]);
}
}
int index=L[m][n];
int lg=index;
char lcs[index+1];
lcs[index] = '\0';
int i=m; int j=n;
while(i>0&&j>0)
{
if(X[i-1]==Y[j-1])
{
lcs[index-1]=X[i-1];
i--; j--; index--;
}
else if(L[i-1][j]>L[i][j-1])
i--;
else
j--;
}
cout<<lg<<"\n";
for(int k=0;k<lg;k++) cout<<lcs[k]<<" ";
}
int main()
{
int m,n; cin>>m>>n;
char A[m];
char B[n];
for(int i=0;i<m;i++) cin>>A[i];
for(int i=0;i<n;i++) cin>>B[i];
lcs(A,B,m,n);
}