Cod sursa(job #260873)

Utilizator yonutzTalos Ionut yonutz Data 17 februarie 2009 17:33:48
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<fstream.h>  
int i,j,n,m,s,sl[1025],a[1025],b[1025],v[1025][1025];  
ifstream f in("cmlsc.in");  
ofstream f out("cmlsc.out");  
void citire()
{  
fin>>n>>m;  
for(i=1;i<=n;i++)  
fin>>a[i];  
for(i=1;i<=m;i++)  
fin>>b[i];  
}  
int max(int a,int b)
{  
   return (a>b)?a:b;  
}  

void din(){  
for(i=1;i<=n;i++)  
for(j=1;j<=m;j++)  
if(a[i]==b[j])  
v[i][j]=1+v[i-1][j-1];  
else  
v[i][j]=max(v[i-1][j],v[i][j-1]);  
i=n;  
j=m;  
while(i>0&&j>0)  
 if(a[i]==b[j])
 {  
  sl[++s]=a[i];  
   i--;  
   j--;  
  }  

 else  
 if(v[i-1][j]>v[i][j-1])  
   i--;  
     else  
     j--;  
f out<<v[n][m]<<'\n';  
for(i=s;i>=1;i--)  
f out<<sl[i]<<" ";  
}  


int main(){  
citire();  
din();  
return 0;     
}