提示: 欢迎访问OurACM平台。
Problem 2024 LCS && EditStep

Accept: 112    Submit: 327
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

给定a,b两个字符串,长度Len(1 <=Len<=1000),分别求出这两个字符串的LCS长度和EditStep。其中:

LCS为两个字符串的最长公共子串。

EditStep为,通过增加一个字符,或者删除一个字符,或者替换一个字符使得a串与b串相同需要的操作个数。

Input

第一行有一个整数,N(1<=N<=50)代表输入数据组数。

接下去,2×N行,每行为一个长度1 <=Len<=1000的字符串。

Output

每组数据输出一行“Case %d: LCS=%d EditStep=%d”,其中第一个%d为输入数据的组数ID,第二个%d为LCS的长度,最后一个%d为EditSetp的步数。

Sample Input

2 abcdxyzk abcdxyzl aekdycoin abcdxyzk

Sample Output

Case 1: LCS=7 EditStep=1 Case 2: LCS=3 EditStep=7

Source

FOJ有奖月赛-2011年04月(校赛热身赛)

Submit  Back  Status  Discuss