C1148 - 最长公共子序列
题目描述
一个序列的子序列是指通过从给定序列中移除某些元素（可能没有移除任何元素）后得到的序列。给定一个序列 X = < x₁, x₂, ..., xₘ >，另一个序列 Z = < z₁, z₂, ..., zₖ > 是 X 的子序列，如果存在一个严格递增的索引序列 < i₁, i₂, ..., iₖ > 满足对所有 j = 1, 2, ..., k，有 xᵢⱼ = zⱼ。例如，Z = < a, b, f, c > 是 X = < a, b, c, f, b, c > 的一个子序列，对应的索引序列为 < 1, 2, 4, 6 >。给定两个序列 X 和 Y，问题是找出 X 和 Y 的最长公共子序列的长度。
输入格式
程序的输入来自标准输入。输入中的每组数据包含两个字符串，表示给定的序列。这两个序列之间由任意数量的空白字符分隔。输入数据均为合法数据。
输入以EOF作为结束标志
输出格式
对于每组数据，程序在标准输出中输出最长公共子序列的长度，每个结果占一行的开头位置。
样例 #1 输入
abcfbc abfcab
programming contest
abcd mnp
样例 #1 输出
4
2
0
数据范围与提示
100%的数据：每个字符串长度在1 - 5000之间
补充说明
字符串中不会包含空格，每个字符串由小写、大写英文字母组成
测试点数目
共10个测试点，每个测试点10分
时间与内存限制
每个测试点时间：1000ms（1.0s），内存：256MiB
输入输出模式
本OJ支持两种输入输出模式
1. 标准输入输出模式：
直接从标准输入和标准输出读写数据，不需要使用freopen进行文件输入输出重定向
2. 文件输入输出模式（国内信奥赛输入输出模式）:
从文件中读写数据，需要使用freopen进行输入输出重定向
本题输入文件名为：C1148.in，输出文件名为：C1148.out