最长公共子序列

题目描述

给定两个字符串 s1 和 s2，长度为 n 和 m 。求两个字符串最长公共子序列的长度。

所谓子序列，指一个字符串删掉部分字符（也可以不删）形成的字符串。

例如：字符串 "arcaea" 的子序列有 "ara" 、 "rcaa" 等。

但 "car" 、 "aaae" 则不是它的子序列。

所谓 s1 和 s2 的最长公共子序列，即一个最长的字符串，它既是 s1 的子序列，也是 s2 的子序列。

输入格式

第一行输入一个整数 n 和 m ，表示字符串 s1 和 s2 的长度。

接下来第二行和第三行分别输入一个字符串 s1 和 s2。

输出格式

输出两个字符串的最长公共子序列的长度

样例 #1

样例输入 #1

5 6
abcde
bcdaaa

样例输出 #1

3

提示

数据范围 : $1\leq m,n\leq1000$ 。保证字符串中的字符只有小写字母。