|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||256 MB||20||8||7||38.889%|
Ahmed Samir Hamza (Hamzawy, a world finalist in the 2013 ICPC in St. Petersburg, a judge in the TCPC and an IBM software engineer), was in a programming interview lately and got asked a puzzling question that he could not answer, so he has asked you to help him to solve it.
Here is the question, given a string S of lowercase English characters, find a string which is a prefix of S, a suffix of S and a substring in S. The three occurrences of this string must not overlap. You should find the longest string which satisfies the above conditions.
A prefix of a string S is a string which can be obtained by deleting zero or more characters from the end of S. A suffix of a string S is a string which can be obtained by deleting zero or more characters from the start of S. A substring of a string S is a string which can be obtained by deleting zero or more characters from the end of S and zero or more characters from the start of S.
Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 100). Followed by T lines, each test case is a single line containing a non-empty string of lowercase English characters (from ‘a’ to ‘z’) containing no more than 106 characters.
For each test case print a single line containing “Case n:” (without the quotes) where n is the test case number (starting from 1) followed by a space then the longest required string, if there is no such string, print -1 instead.
2 barbararhubar barbararhuaar
Case 1: bar Case 2: -1