가장 긴 공통부분 팰린드롬

시간 제한1초메모리 제한512 MB

요약

길이 합이 100만 이하인 최대 50개의 문자열이 주어질 때, 모든 문자열에 공통으로 부분 문자열로 나타나는 가장 긴 팰린드롬의 길이를 구한다.

문제

알파벳 소문자로만 이루어진 문자열 n개가 주어진다. n개의 문자열 모두에 부분 문자열로 포함되어 있는 팰린드롬 중에서 길이가 가장 긴 것을 찾아 그 길이를 출력하는 프로그램을 작성하시오.

부분 문자열(substring)이란 문자열에서 연속된 구간을 잘라낸 문자열을 뜻한다.

팰린드롬이란 뒤집은 문자열이 원래 문자열과 같아지는 문자열을 뜻한다. 예를 들어 "ababa"는 팰린드롬이지만 "abcbd"는 팰린드롬이 아니다.

첫 번째 줄에 문자열의 개수를 나타내는 자연수 n이 주어진다. ( $1 \le n \le 50$ )

두 번째 줄부터 n개의 줄에 걸쳐 문자열이 하나씩 주어진다. 모든 문자열은 알파벳 소문자로만 이루어져 있으며 빈 문자열은 주어지지 않는다. n개 문자열의 길이 합은 $1,000,000$ 이하이다.

첫 번째 줄에 문제의 정답을 출력한다. n개의 문자열 모두에 포함된 팰린드롬이 존재하지 않으면 0을 출력한다.