#197. 最长公共子序列

题目类型:传统型 时间限制:1000 ms 空间限制:256 MiB
输入文件:标准输入 输出文件:标准输出 答案检查器:文本比较

这是一道模板题。

给你两个字符串,请输出它们的最长公共子序列


输入格式

第一行两个整数 $n$ 和 $m$,分别表示两个字符串的长度。

第二行一个长度为 $n$ 的字符串 $A$。

第三行一个长度为 $m$ 的字符串 $B$。

输出格式

一行一个整数,表示 $A$ 和 $B$ 的最长公共子序列。


样例一

Input

16 14
gcttgcctacattctg
tagcttaagatctt

Output

9

Explanation

最长公共子序列为 gcttaattt。


限制与约定

对于 $100\%$ 的数据,满足 $1\ \leq\ n,\ m\ \leq\ 50000$,保证输入中字符串均由小写英文字母构成。

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$