Wise cyt has got a string S with N (1 ≤ N ≤ 10^5 ) characters. All the characters of S are lowercase or uppercase English letters. Now he challenges Xingxing to find out a string T of length N such that the length of the LCS (Longest Common Subsequence) of S and T is minimum. T also should be consisted of lowercase or uppercase English letters only. Now it is Xingxing’s problem to find out the string T. But you need to print the minimum length of such LCS given that Xingxing has found T correctly.
1168: Water Problem: LCS
时间限制: 2 Sec 内存限制: 128 MB提交: 148 解决: 50
[提交][状态][讨论版]
题目描述
输入
Input file starts with a single integer T (1 ≤ T ≤ 50), T test cases following. Each of the next T test cases has one string S on a line.
输出
For each case print your output in format, ‘Case X: Y ’, on a single line where X denotes the case number starting from 1 and Y denotes the length of the shortest possible LCS.
样例输入
2
ab
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ
样例输出
Case 1: 0
Case 2: 1
提示
Subsequence can be not constant.
来源
한국어
中文
فارسی
English
ไทย
Anything about the Problems, Please Contact Admin:admin
All Copyright Reserved 2010-2021 Xidian Programming Contest Online Judge TEAM
GPL2.0 2003-2014 HUSTOJ Project TEAM
Anything about the Problems, Please Contact Admin:admin
All Copyright Reserved 2010-2021 Xidian Programming Contest Online Judge TEAM
GPL2.0 2003-2014 HUSTOJ Project TEAM