← 返回题目列表

Codeforces · 164/B

B. 古代贝尔兰象形文字

中文机器翻译题面 查看原题

Polycarpus 喜欢研究 Berland 象形文字。有一次波利卡普得到了两幅古老的贝尔兰图画,每幅图画上都画着一圈象形文字。我们知道,没有象形文字在第一个或第二个圆圈中出现两次(但在每个圆圈中可以出现一次)。

Polycarpus 想将这些图片保存在他的笔记本电脑上,但问题是,笔记本电脑不允许写象形文字圆圈。因此波利卡普必须打破每个圆圈,并按顺时针顺序在一行中写下所有象形文字。从第一个圆得到的线称为a,从第二个圆得到的线称为b。

打破象形文字圈的方法有很多,因此 Polycarpus 选择了一种方法,即使字符串 a 的最大子串(作为字符串 b 中的子序列出现)的长度最大。

Help Polycarpus — 如果第一个和第二个圆圈被最佳地打破,找到所需子串(子序列)的最大可能长度。

字符串 s 的长度是其中的字符数。如果我们将字符串 s 的长度表示为 |s|,则可以将字符串写为 s = s1s2... s|s|。

s 的子字符串是非空字符串 x = s[a... b] = sasa + 1... sb (1 ≤ a ≤ b ≤ |s|)。例如,“code”和“force”是“codeforces”的子字符串,而“coders”则不是。

s 的子序列是非空字符串 y = s[p1p2... p|y|] = sp1sp2... sp|y| (1 ≤ p1 < p2 < ... < p|y| ≤ |s|)。例如,“coders”是“codeforces”的子序列。

输入

第一行包含两个整数 la 和 lb (1 ≤ la, lb ≤ 1000000) — 分别是第一圈和第二圈中象形文字的数量。

下面,由于 Berland 象形文字的编码困难,它们以 1 到 106 之间的整数给出。

第二行包含 la 整数 - 第一张图片中的象形文字,按顺时针顺序,从其中一个开始。

第三行包含 lb 整数 - 第二张图片中的象形文字,按顺时针顺序,从其中一个开始。

保证第一个圆圈不包含出现两次的象形文字。第二个圆也有这个性质。

输出

打印单个数字——公共子串和子序列的最大长度。如果任何打破圆圈的方式都不存在,则打印 0。

示例

输入 #1

5 4
1 2 3 4 5
1 3 5 6

输出 #1

2

输入 #2

4 6
1 3 5 2
1 2 3 4 5 6

输出 #2

3

输入 #3

3 3
1 2 3
3 2 1

输出 #3

2

注意

在第一个测试中,Polycarpus 选择了一个由象形文字 5 和 1 组成的字符串,而在第二个样本中,则选择了由象形文字 1、3 和 5 组成的字符串。