402. 最长公共子序列LCS
时间限制：1000 MS 内存限制：128 MB
题目描述
# 最长公共子序列LCS ## 题目描述 给定两个长度分别为 $N$ 和 $M$ 的字符串 $A$ 和 $B$，求它们的最长公共子序列的长度。 一个字符串的子序列，是从该字符串中删除零个或多个字符，并保持剩余字符的相对顺序所得到的序列。子序列中的字符不必在原字符串中连续。 如果一个序列既是 $A$ 的子序列，也是 $B$ 的子序列，则称它为 $A$ 和 $B$ 的公共子序列。 ## 输入格式 从文件 `lcs.in` 中读入数据。 第一行包含两个整数 $N$ 和 $M$，分别表示字符串 $A$ 和 $B$ 的长度。 第二行包含一个长度为 $N$ 的字符串 $A$。 第三行包含一个长度为 $M$ 的字符串 $B$。 ## 输出格式 将答案输出到文件 `lcs.out`。 输出一个整数，表示 $A$ 和 $B$ 的最长公共子序列的长度。 ## 数据范围 - $1 \le N,M \le 1000$。 - 字符串 $A$ 和 $B$ 均仅由小写英文字母组成。 ## 样例输入 ``` 4 5 acbd abedc ``` ## 样例输出 ``` 3 ``` ## 样例说明 `abd` 是两个字符串的公共子序列，长度为 $3$，且不存在更长的公共子序列。 ## 时间与内存限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$128$ MB。