#2571. 最长公共子序列(poj)

最长公共子序列(poj)

题目描述

序列的子序列指序列中的一些元素被省略。

给定一个序列xx==<<x1x_1,x2x_2,…,xmx_m>及另一个序列zz==<<z1z_1,z2z_2…,zkz_k>,若xx的索引存在严格递增的序列<<i1i_1,i2i_2,…,iki_k>,则对所有jj==11,22,…,kkxijx_{ij}==zjz_jzz都是xx的子序列。

例如,zz==<<aa,bb,ff,cc>的索引序列是<<11,22,44,66>,它是xx==<<aa,bb,cc,ff,bb,cc>的子序列。

zz既是xx的子序列,也是yy的子序列,则称zzxxyy的公共子序列。

给定两个序列xxyy,求xxyy的最长公共子序列的长度。

输入格式

每个测试用例都包含两个表示给定序列的字符串,序列由任意数量的空格分隔。

输出格式

对每个测试用例,都单行输出最长公共子序列的长度。

样例

abcfbc abfcab
programming contest
abcd mnp
4
2
0

来源

POJ1458