Problem 24344 --最长公共子序列LCS(一本通9.23)

24344: 最长公共子序列LCS(一本通9.23)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 3  Solved: 2
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][84kb]

Description

最长公共子序列LCS(Longest Common Subsequence)

【LCS开篇案例】

序列:X={A,B,C,B,D,A,B}

序列:Y={B,C,D,B,A}

序列:Z={B,C,D,B}

序列:W={B,C,D}

Z是(X与Y)的最长公共子序列(Longest-Common-Subsequence),而W虽然是X与Y的公共子序列,但是不是最长的!

【LCS晦涩定义】

给定一个序列X={x1,x2,x3...xm},另一个序列Z={z1,z2,z3...zk}为子序列,如果存在X的

一个严格递增下标序列<i1,i2,i3,i4...ik>,使得所有的j=1,2,...,k,有x[i<j>]=z[j]

例如,Z={B,C,D,B}是X={A,B,C,B,D,A,B}一个最长子序列,相应的下标序列为<2,3,5,7>

如果Z同时是Y的最长子序列,那么Z就是X与Y的最长公共子序列


【输入样例】

ABCBDAB

BDCABA

【输出样例】

4


【说明】 输入两行字符,输出LCS长度



Input

Output

HINT

Source

[Submit][Status]