Pagini recente » Cod sursa (job #1884849) | Cod sursa (job #1528779) | Cod sursa (job #3221792) | Cod sursa (job #381839) | Cod sursa (job #2445112)
#include <bits/stdc++.h>
using namespace std;
template <class T>
class longestCommonSubsequence
{
private:
#define pb push_back
#define maxx(a,b) (a)>(b)?(a):(b)
#define uint unsigned int
std::vector<T>sa, sb;
public:
void addElementA(T &val)
{
sa.push_back(val);
}
void addElementB(T &val)
{
sb.push_back(val);
}
void resetA()
{
sa.clear();
}
void resetB()
{
sb.clear();
}
void reset()
{
resetA();
resetB();
}
uint getLCSLen()
{
std::vector<uint> dp[2];
dp[0].resize(sb.size() + 1, 0);
dp[1].resize(sb.size() + 1, 0);
for (uint i=0; i<sa.size(); ++i)
{
dp[i%2][0] = (sa[i] == sb[0] ? 1 : 0);
for (uint j=1; j<sb.size(); ++j)
if (sa[i] == sb[j])
dp[i%2][j] = dp[!(i%2)][j-1] + 1;
else
dp[i%2][j] = maxx(dp[!(i%2)][j], dp[i%2][j-1]);
}
return dp[!(sa.size()%2)][sb.size()-1];
}
void getLCS(std::vector<T> &ans)
{
std::vector<std::vector<uint>>dp;
dp.resize(sa.size());
for (uint i=0; i<sa.size(); ++i)
dp[i].resize(sb.size(), 0);
dp[0][0] = (sa[0] == sb[0] ? 1 : 0);
for (uint j=1; j<sb.size(); ++j)
if (sa[0]==sb[j]) dp[0][j] = 1;
else
dp[0][j] = dp[0][j-1];
for (uint i=1; i<sa.size(); ++i)
{
dp[i][0] = (sa[i] == sb[0] ? 1 : 0);
for (uint j=1; j<sb.size(); ++j)
if (sa[i] == sb[j])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = maxx(dp[i-1][j], dp[i][j-1]);
}
ans.clear();
for (int i=sa.size()-1, j=sb.size()-1; i>=0&&j>=0;)
if (sa[i] == sb[j])
{
ans.push_back(sa[i]);
--i, --j;
}
else if (i==0)--j;
else if (j==0)--i;
else if (dp[i-1][j] > dp[i][j-1])--i;
else --j;
}
};
int main()
{
freopen("cmlsc.in","r",stdin);
freopen("cmlsc.out","w",stdout);
int n, m, x;
longestCommonSubsequence<int> lcs;
scanf("%d %d",&n,&m);
for (int i=1; i<=n; ++i)
{
scanf("%d",&x);
lcs.addElementA(x);
}
for (int i=1; i<=m; ++i)
{
scanf("%d",&x);
lcs.addElementB(x);
}
vector<int>ans;
lcs.getLCS(ans);
reverse(ans.begin(), ans.end());
printf("%u\n", ans.size());
for (auto x:ans)
printf("%d ", x);
printf("\n");
return 0;
}