6406: 最长公共子序列
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：4
解决：1
题目描述
序列的子序列指序列中的一些元素被省略。
给定一个序列$x$$=$$<$$x_1$,$x_2$,…,$x_m$>及另一个序列$z$$=$$<$$z_1$,$z_2$…,$z_k$>，若$x$的索引存在严格递增的序列$<$$i$$1$,$i$$2$,…,$i$$k$>，则对所有$j$$=$$1$,$2$,…,$k$及$x_{ij}$$=$$z_j$，$z$都是$x$的子序列。
例如，$z$$=$$<$$a$,$b$,$f$,$c$>的索引序列是$<$$1$,$2$,$4$,$6$>，它是$x$$=$$<$$a$,$b$,$c$,$f$,$b$,$c$>的子序列。
若$z$既是$x$的子序列，也是$y$的子序列，则称$z$是$x$和$y$的公共子序列。
给定两个序列$x$和$y$，求$x$和$y$的最长公共子序列的长度。
给定一个序列$x$$=$$<$$x_1$,$x_2$,…,$x_m$>及另一个序列$z$$=$$<$$z_1$,$z_2$…,$z_k$>，若$x$的索引存在严格递增的序列$<$$i$$1$,$i$$2$,…,$i$$k$>，则对所有$j$$=$$1$,$2$,…,$k$及$x_{ij}$$=$$z_j$，$z$都是$x$的子序列。
例如，$z$$=$$<$$a$,$b$,$f$,$c$>的索引序列是$<$$1$,$2$,$4$,$6$>，它是$x$$=$$<$$a$,$b$,$c$,$f$,$b$,$c$>的子序列。
若$z$既是$x$的子序列，也是$y$的子序列，则称$z$是$x$和$y$的公共子序列。
给定两个序列$x$和$y$，求$x$和$y$的最长公共子序列的长度。
输入
多组数据。
每个测试用例都包含两个表示给定序列的字符串，序列由任意数量的空格分隔。
每个测试用例都包含两个表示给定序列的字符串，序列由任意数量的空格分隔。
输出
对每个测试用例，都单行输出最长公共子序列的长度。
样例输入 复制
abcfbc abfcab
programming contest
abcd mnp样例输出 复制
4
2
0