跳至正文
题库3972
#3972

1297. 公共子序列

查看题目操作

1297. 公共子序列

题目描述

我们称序列 Z=⟨z1,z2,…,zk⟩Z=\langle z_1, z_2, \ldots, z_k \rangle 是序列 X=⟨x1,x2,…,xm⟩X=\langle x_1, x_2, \ldots, x_m \rangle 的子序列,当且仅当存在严格上升的序列 ⟨i1,i2,…,ik⟩\langle i_1, i_2, \ldots, i_k \rangle,使得对 j=1,2,…,kj=1,2,\ldots,k,有 xij=zjx_{i_j}=z_j。比如 Z=⟨b,c,b⟩Z=\langle b, c, b \rangle 是 X=⟨a,b,c,b,d⟩X=\langle a, b, c, b, d \rangle 的子序列。

现在给出两个序列X和Y,你的任务是找到X和Y的最大公共子序列,也就是说要找到一个最长的序列Z,使得Z既是X的子序列也是Y的子序列。

输入格式

输入包括多组测试数据。每组数据包括一行,给出两个长度不超过200的字符串,表示两个序列。两个字符串之间由若干个空格隔开。

输出格式

对每组输入数据,输出一行,给出两个序列的最大公共子序列的长度。

abcfbc abfcab
programming contest
abcd mnp
4
2
0

来源

一本通在线评测 ybtbas-1297