问题 1168. -- Water Problem: LCS

1168: Water Problem: LCS

时间限制: 2 Sec  内存限制: 128 MB
提交: 122  解决: 40
[提交][状态][讨论版]

题目描述

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.

输入

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.

来源

RiseAbove

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