Problem 21583 --最长公共子序列

21583: 最长公共子序列

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

Description

  最长公共子序列,英文缩写为LCS(Longest Common Subsequence)。其定义是,一个序列 S ,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。

  最长公共子序列是一个十分实用的问题,它可以描述两段文字之间的“相似度”,即它们的雷同程度,从而能够用来辨别抄袭。对一段文字进行修改之后,计算改动前后文字的最长公共子序列,将除此子序列外的部分提取出来,这种方法判断修改的部分,往往十分准确。

     给出两段文字,求最长公共子序列长度。

  

Input

两行:

第1行:一行字符串

第2行:一行字符串

字符串长度均不超过1000。

Output

一行:一个整数,表示LCS长度。

Sample Input

ABCDEFG
CABXCEDGEF

Sample Output

6

HINT

【样例解释】最长上升子序列为:ABCDEF,长度为6。

Source

[Submit][Status]