Home => ProblemSet => 2.12-12:最长公共子序列
Problem1323--2.12-12:最长公共子序列

1323: 2.12-12:最长公共子序列

Time Limit: 1 Sec  Memory Limit: 128 MB  Submit: 1  Solved: 5
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

给定两个长度分别为N和M的字符串A和B，求既是A的子序列又是B的子序列的字符串长度最长是多少。

Input

第一行包含两个整数N和M。
第二行包含一个长度为N的字符串，表示字符串A。
第三行包含一个长度为M的字符串，表示字符串B。
字符串均由小写字母构成。

Output

输出一个整数，表示最大长度。

Sample Input Copy 

4 5
acbd
abedc

Sample Output Copy 

3

HINT

对于 100%的数据1≤N,M≤1000

Source/Category

算法 枚举 动态规划 线性 
[ Submit ] [ Status ]