Cod sursa(job #809274)
| Utilizator | Data | 8 noiembrie 2012 08:36:12 | |
|---|---|---|---|
| Problema | Cel mai lung subsir comun | Scor | 30 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 1.26 kb |
#include <cstdio>
using namespace std;
int a[100],b[100],n,i,j,m,LCS[100][100],OP[100][100];
int main(){
freopen("cmlsc.in","r",stdin);
freopen("cmlsc.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i){
scanf("%d",&a[i]);
}
for(j=1;j<=m;++j){
scanf("%d",&b[j]);
}
for(i=n;i>=1;--i){
for(j=m;j>=1;--j){
if(a[i]==b[j]){
LCS[i][j]=1+LCS[i+1][j+1];
OP[i][j]=1;
}
else{
if(a[i]!=b[j]){
if(LCS[i+1][j]>LCS[i][j+1]){
LCS[i][j]=LCS[i+1][j];
OP[i][j]=2;
}
else{
LCS[i][j]=LCS[i][j+1];
OP[i][j]=3;
}
}
}
}
}
printf("%d\n",LCS[1][1]);
i=1;
j=1;
while(OP[i][j]!=0){
if(OP[i][j]==1){
printf("%d ",a[i]);
++i;
++j;
}
else{
if(OP[i][j]==2){
++i;
}
else{ ++j;}
}
}
return 0;
}
