Наибольшая общая подпоследовательность с восстановлением ответа
вот проблема
Даны две последовательности, требуется найти и вывести их наибольшую общую подпоследовательность.
Входные данные В первой строке входных данных содержится число N – длина первой последовательности (1 ≤ N ≤ 1000). Во второй строке заданы члены первой последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.
В третьей строке записано число M – длина второй последовательности (1 ≤ M ≤ 1000). В четвертой строке задаются члены второй последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.
Выходные данные Требуется вывести наибольшую общую подпоследовательность данных последовательностей, через пробел.
вот что я пробовал
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
using namespace std;
const int N = 1002;
int x[N], y[N], a[N][N];
int main() {
//ios_base::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
int n, m;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> x[i];
}
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> y[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (x[i] == y[j]) {
a[i][j] = 1 + a[i - 1][j - 1];
}
else {
a[i][j] = max(a[i - 1][j], a[i][j - 1]);
}
}
}
vector<int> v;
int i = n, j = m;
while (i && j) {
if (x[i - 1] == y[j - 1]) {
v.push_back(x[i]);
i--;
j--;
}
else if (a[i - 1][j] == a[i][j]) {
i--;
}
else {
j--;
}
}
for (int k = v.size() - 1; k >= 0; k--) {
cout << v[k] << ' ';
}
return 0;
}
во первых: выводит неправильный ответ(к примеру в случаи следующих входных данных 3 1 2 3 3 2 3 1, выводит 3 вместо 2 3 )
во вторых:выдает следующие предупреждения:
