Cod sursa(job #2368248)
| Utilizator | Data | 5 martie 2019 14:47:29 | |
|---|---|---|---|
| Problema | Cel mai lung subsir comun | Scor | 0 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.96 kb |
#include <fstream>
#include <iostream>
using namespace std;
#define N 1025
ifstream f("cmlsc.in");
ofstream g("cmlsc.out");
int x1[N],x2[N],a[N][N],n,m,sol[N],poz;
int main()
{
f>>n>>m;
int i,j;
for(i=1;i<=n;i++)
f>>x1[i];
for(i=1;i<=m;i++)
f>>x2[i];
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(x1[i]==x2[j])
{
a[i][j]=1+a[i-1][j-1];
}
else
{
a[i][j]=max(a[i-1][j],a[i][j-1]);
}
}
}
for(i=n,j=m;a[i][j];)
{
if (x1[i] == x2[j])
{
++poz;
sol[poz]= x1[i];
--i;--j;
}
else
if (a[i-1][j] < a[i][j-1])
--j;
else
--i;
}
g<<poz+1<<"\n";
for(i=poz;i>0;--i)
g<<sol[i]<<" ";
return 0;
}
