왕복 노선의 대표 문자열

문제

버스 노선 조사팀은 차량이 지나간 정류장을 알파벳 대문자로 기록한다. 이 조사에서 각 문자는 하나의 정류장을 나타내며, 서로 다른 문자는 서로 다른 정류장이다. 차량이 같은 정류장에 머무는 동안 기록 장치가 여러 번 작동할 수 있으므로, 원본 문자열에는 같은 문자가 연속으로 나타날 수 있다. 조사팀은 이러한 반복 기록과 운행 방향을 정리하여 가장 자주 관측된 노선 형태를 찾으려 한다. 먼저 원본 문자열에서 같은 문자가 연속으로 이어진 각 구간을 문자 하나로 바꾼다. 예를 들어 AAACCBBA를 정리하면 ACBA가 된다. 연속하지 않은 같은 문자는 합치지 않는다. 따라서 ABCA의 처음과 마지막에 있는 A는 모두 남는다. 이 과정을 거친 문자열을 정차 순서라고 부른다. 조사팀은 정차 순서와 그것을 뒤집은 문자열을 같은 노선 형태로 취급한다. 왕복 운행을 하나로 묶기 위한 규칙이다. 각 기록의 대표 문자열은 정차 순서와 그 역순 문자열 가운데 사전순으로 앞선 것이다. 두 문자열이 같다면 그 문자열 자체를 대표 문자열로 사용한다. 사전순은 A부터 Z까지의 문자 순서를 따르며, 한 문자열이 다른 문자열의 접두사라면 길이가 짧은 문자열이 앞선다. 각 원본 기록은 대표 문자열 하나에 정확히 한 번 기여한다. 원본 문자열이 완전히 같거나, 정리한 결과가 같은 기록이 반복되어도 기록마다 횟수를 따로 센다. 서로 다른 대표 문자열의 횟수를 합치지는 않는다. 기록은 적어도 하나 있고 빈 문자열은 주어지지 않으므로 대표 문자열도 항상 하나 이상 존재한다. 모든 기록을 처리한 뒤 등장 횟수가 가장 큰 대표 문자열을 찾는다. 최대 등장 횟수를 가진 대표 문자열이 여러 개라면 사전순으로 가장 앞선 것을 선택한다. 선택한 대표 문자열과 그 등장 횟수를 출력한다.

입력

첫째 줄에 기록 수 N이 주어진다. N은 1 이상 10,000 이하의 정수다.
다음 N개 줄에는 원본 문자열이 하나씩 주어진다. 각 문자열은 알파벳 대문자 A부터 Z로만 이루어지며 길이는 1 이상 20 이하의 정수다.

출력

첫째 줄에 선택한 대표 문자열을 출력한다. 둘째 줄에 그 대표 문자열의 등장 횟수를 정수로 출력한다.

5
ABBCCB
BCCBBA
AAD
DDAA
C

ABCB
2

3
ZZZ
Z
ZZZZ

Z
3

출처: Devin.KR 자체 제작