链接: https://cses.fi/problemset/task/3403

板块: Dynamic Programming

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定两个整数数组，求它们的最长公共子序列。

子序列是指从数组中按从左到右顺序取出、但允许有间隔的元素序列。公共子序列是指同时出现在两个数组中的子序列。

输入

第一行包含两个整数 $n$ 和 $m$：两个数组的大小。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$：第一个数组的内容。

第三行包含 $m$ 个整数 $b_1,b_2,\dots,b_m$：第二个数组的内容。

输出

首先输出最长公共子序列的长度。

然后输出一个这样的序列示例。如果有多种方案，输出任意一种即可。

数据范围

$1 \le n,m \le 1000$ $1 \le a_i, b_i \le 10^9$

样例输入

8 6
3 1 3 2 7 4 8 2
6 5 1 2 3 4

样例输出

3
1 2 4