Pagini recente » Cod sursa (job #1513522) | Cod sursa (job #1661922) | Cod sursa (job #695113) | Cod sursa (job #2299806) | Cod sursa (job #3272465)
#include <fstream>
#include <vector>
using namespace std;
int n,m;
const int maxn=700;
int v1[maxn],v2[maxn];
struct sigma{
int lungime;
vector<int> numere;
};
sigma dp[maxn][maxn];
int cnt[maxn][maxn];
void lcs(int i,int j){
if(cnt[i][j]==1)return;
if(i==0 || j==0)return;
cnt[i][j]=1;
if(v1[i]==v2[j]){
lcs(i-1,j-1);
if(dp[i][j].lungime<dp[i-1][j-1].lungime+1){
dp[i][j].lungime=dp[i-1][j-1].lungime+1;
dp[i][j].numere=dp[i-1][j-1].numere;
dp[i][j].numere.push_back(v1[i]);
}
return;
}else{
lcs(i,j-1);
lcs(i-1,j);
if(dp[i][j].lungime<dp[i][j-1].lungime){
dp[i][j].lungime=dp[i][j-1].lungime;
dp[i][j].numere=dp[i][j-1].numere;
}
if(dp[i][j].lungime<dp[i-1][j].lungime){
dp[i][j].lungime=dp[i-1][j].lungime;
dp[i][j].numere=dp[i-1][j].numere;
}
return;
}
}
int main()
{
ifstream cin("cmlsc.in");
ofstream cout("cmlsc.out");
cin>>n>>m;
for (int i = 1; i <=n; i++) {
cin>>v1[i];
}
for (int i = 1; i <=m; i++) {
cin>>v2[i];
}
lcs(n,m);
cout<<dp[n][m].lungime<<'\n';
for(auto i:dp[n][m].numere)cout<<i<<" ";
return 0;
}