Cod sursa(job #1228408)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 14 septembrie 2014 08:32:12
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <cstdio>
#define max_l 1024
using namespace std;
int n,m,a[max_l],b[max_l];
int lcs[max_l][max_l];
int s[max_l],bst;
int max(int x,int y){
if(x>y)return x;
return y;
}
int main(void){
freopen("cmlsc.in","r",stdin);
freopen("cmlsc.out","w",stdout);
scanf("%d%d",&n,&m);
int i=1,j;
while(i<=m)
scanf("%d",&a[i++]);
i=1;
while(i<=n)
scanf("%d",&b[i++]);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(a[i]==b[j])
lcs[i][j]=lcs[i-1][j-1]+1;
else          
lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1]);
for(i=m;j=n;i){
if(a[i]==b[j]){
s[++bst]=a[i];
--i;--j;
}
else 
if(lcs[i-1][j]>lcs[i][j-1])
i--;
else
j--;
}
printf("%d\n",bst);
for(i=bst;i>0;i--)
printf("%d ",s[i]);
}