题目描述

给定一个长度为 $n$ 的序列 $A$，以及一个长度为 $m$ 的序列 $B$，求 $A,B$ 的最长公共子序列。即求一个最长的序列，保证既是 $A$ 的子序列又是 $B$ 的子序列。

保证 $A,B$ 中都只包含小写英文字母。

• 子序列：序列 $A$ 的子序列是从 $A$ 中将若干元素提取出来并不改变相对位置形成的序列。空序列及原序列本身也是原序列的一个子序列。
• 非空子序列：除了空序列之外的子序列。
• 真子序列：除了原序列本身之外的子序列。
• 非空真子序列：除了空序列及原序列本身之外的子序列。

输入格式

第一行两个数 $n,m$。

第二行 $n$ 个小写英文字母 $a_1\sim a_n$。

第三行 $m$ 个小写英文字母 $b_1\sim b_m$。

输出格式

一个整数，即最长公共子序列的长度。

5 5
abccd
bcacd

4

bccd

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 5000$, $1\le m\le 5\times 10^5$，