문제
알파벳 소문자로만 이루어진 문자열을 생각해 보자. 접두사란 부분 문자열 중 시작 부분이 가장 앞인 문자열을 의미한다. 접미사란 부분 문자열 중 끝 부분이 가장 뒤인 문자열을 의미한다. 특별히, 빈 문자열은 접두사이면서 접미사이다. 한 문자열의 접두사를 떼어낸 뒤 가장 뒤로 옮기는 것으로 다른 문자열을 만들 수 있다면, 두 문자열은 주기적 동형 관계라고 한다. 예를 들어, ababba와 abbaab는 주기적 동형 관계이나, ababba와 ababab는 아니다. 특별히, 모든 문자열은 자기 자신과 주기적 동형 관계에 있다.
길이 n인 문자열 t가 주어진다. 우리는 이 문자열에서 다음 조건을 만족하는 같은 길이의 접두사 p와 접미사 s를 찾을 것이다.
p와 s는 주기적 동형 관계에 있어야 하며, p와 s의 길이는 n/2을 넘을 수 없고 (p와 s는 t 안에서 겹칠 수 없다), p와 s의 길이의 합은 최대가 되어야 한다.
입력
첫 번째 줄에 문자열 t의 길이를 나타내는 정수 n (1 ≤ n ≤ 1,000,000) 이 주어진다. 두 번째 줄에 문자열 t가 알파벳 소문자 n개로 주어진다.
출력
첫 번째 줄에 접두사 p와 접미사 s의 길이의 최댓값을 출력한다.
예제
15
ababbabababbaab
6
출처
Polish Olympiad in Informatics 2011/2012 - Stage 3 - 6번
로그인해야 코드를 작성할 수 있어요.