Comet OJ

C1652 [Wannafly冬令营2018Day2]Square Subsequences

内存限制：256 MB 时间限制：1000 ms

题目描述

小 Q 有一个字符串 $s_{1} s_2 \cdots s_n$，他想找出其中最长的子序列使得这个子序列能够表示成平方串，你能帮他找出来吗？

$s_{1} s_2 \cdots s_n$ 的每个子序列可以用字符串 $s_{p_1} s_{p_2} \cdots s_{p_m}$ 表示，其中 $1 \leq p_1 < p_2 < \cdots < p_m \leq n$。

字符串 $t_{1} t_2 \cdots t_m$ 是平方串当且仅当：

  • $m$ 是偶数；
  • 对于 $i = 1, 2, \cdots, \frac{m}{2}$，有 $t_i = t_{i + \frac{m}{2}}$。

对于样例的最后一组测试数据，最长平方串子序列也可以是baba。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。随后的内容是各组测试数据。对于每组测试数据：

仅一行，包含一个由小写字母组成、长度为 $n$ 的字符串 $s_{1} s_2 \cdots s_n$。

  • $1 \leq T, n \leq 3000$
  • 所有测试数据的 $n$ 之和不超过 $3000$。

输出

对于每组测试数据，首先输出一行Case #x: m，其中x是测试数据的编号（从 $1$ 开始编号），m是最长平方串子序列的长度。

如果m为正，再输出一行，包含一个字符串，表示这个最长平方串子序列。如果有多种最优解，请输出任意一种。

样例

样例输入 1

5
abba
abbab
abac
abcd
bbabab

样例输出 1

Case #1: 2
aa
Case #2: 4
abab
Case #3: 2
aa
Case #4: 0
Case #5: 4
bbbb

提示