最大共通部分配列の長さ

整数配列 ab が与えられたとき、両方の配列に共通して現れる部分配列の中で、最も長いものの長さを求めます。

入力

最初の行には、整数 n (1 ≤ n ≤ 1000) が1つ与えられます。

2行目には、n 個の整数 (0 ≤ ≤ 100) がスペース区切りで与えられます。

3行目には、n 個の整数 (0 ≤ ≤ 100) がスペース区切りで与えられます。

出力

共通部分配列の最大長を出力してください。

入力

出力

4
1 2 4 2
0 4 2 1

2

3
5 5 5
5 5 5

3

解説

  1. 与えられた2つの配列に共通して含まれる最も長い部分配列は 4 2 で、その長さは2です。

  2. 2つの配列が同一のため、最も長い部分配列は配列全体となり、長さは3です。

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue