问题 21583 --最长公共子序列

21583: 最长公共子序列

时间限制: 1 Sec  内存限制: 128 MB
提交: 33  解决: 25
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][44kb]

题目描述

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

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

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

  

输入

两行:

第1行:一行字符串

第2行:一行字符串

字符串长度均不超过1000。

输出

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

样例输入

ABCDEFG
CABXCEDGEF

样例输出

6

提示

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

来源

[提交][状态]