#35. 最长公共子序列

内存限制:1024 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

对于两个给定的序列,请求出它们的最长公共子序列长度。

一个序列的子序列定义为能通过删除一部分元素,保留剩下的元素相对顺序不变而得到的序列。

输入格式

第一行两个整数 n,m ,表示两个序列的长度。

第二行 n 个整数 a_1,a_2, \ldots ,a_n ,表示第一个序列。

第二行 m 个整数 b_1,b_2, \ldots ,b_m ,表示第二个序列。

输出格式

输出两个序列的最长公共子序列长度。

样例

样例输入

4 5
1 2 4 5
4 1 3 3 2

样例输出

2

数据范围与提示

本题共有两个子任务。

对于所有数据, 1 \leq n,m,a_i,b_i \leq 70000

Subtask 1(50分): n,m \leq 5000

Subtask 2(50分):无特殊限制。