제곱 부분문자열
시간 제한0.5초메모리 제한1024 MB
각 문자열에서 앞 절반과 뒤 절반이 같은 제곱 문자열인 가장 긴 부분 문자열을 찾아 길이와 함께 출력한다.
문제
길이가 2n인 문자열 T에 대해, T의 길이 n 접두사와 길이 n 접미사가 같을 경우 T를 제곱 문자열이라고 한다. 빈 문자열은 제곱 문자열이다.
문자열 S가 주어질 때, S의 부분 문자열이면서 제곱 문자열인 최대 길이 문자열을 출력하라. S의 부분 문자열은, S에서 몇 개의 문자를 제거하고 나머지 문자들의 순서를 바꾸지 않은 문자열을 뜻한다.
입력
첫 번째 줄에 테스트 케이스의 개수 T가 주어진다.
이후 T개의 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있다.
각 문자열의 길이는 1 이상 3000 이하이며, 주어지는 모든 문자열의 길이 합은 3000 이하이다.
출력
각 테스트 케이스에 대해서 다음과 같이 출력하라:
만약 정답이 빈 문자열이면, Case #T: 0 을 한 줄에 출력하라.
만약 정답이 빈 문자열이 아니면, Case #T: L을 첫 줄에 출력하고, 다음 줄에 정답을 출력하라.
T는 테스트 케이스의 번호 (1부터 시작)이고, L은 정답 문자열의 길이를 뜻한다.