主页 讨论版 问题 名次 状态 统计

请自觉遵守比赛规则，违者严惩，不接受求情！
问题 A: Water Problem: LCS

问题 A: Water Problem: LCS

时间限制:2000 ms 内存限制:128 MB
提交:148 解决:50
[ 提交][ 状态][ 讨论版]

题目描述

Wise cyt has got a stringSwithN(1 ≤ N ≤ 10^5 ) characters. All the characters ofSare lowercase or uppercase English letters. Now he challenges Xingxing to find out a stringTof lengthNsuch that the length of the LCS (Longest Common Subsequence) ofSandTis minimum.Talso should be consisted of lowercase or uppercase English letters only. Now it is Xingxing’s problem to find out the stringT. But you need to print the minimum length of such LCS given that Xingxing has foundTcorrectly.

输入

Input file starts with a single integerT(1 ≤ T ≤ 50),Ttest cases following. Each of the nextTtest cases has one stringSon a line.

输出

For each case print your output in format, ‘CaseX:Y’, on a single line whereXdenotes the case number starting from 1 andYdenotes the length of the shortest possibleLCS.

样例输入

2 ab abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

样例输出

Case 1: 0 Case 2: 1

提示

Subsequence can be not constant.

[ 提交][ 状态][ 讨论版]
Baidu
map