고고학자 민우는 고대 사원의 벽면에서 아주 긴 비문을 발견했다. 이 비문은 알파벳 소문자로만 이루어진 하나의 문자열로 표현된다.

민우는 이 고대 언어의 문법 구조와 고유 단어를 파악하기 위해, 비문 내에서 최소 두 번 이상 등장하는 부분 문자열 중 가장 긴 것의 길이를 찾으려고 한다.

이때, 두 번 등장하는 부분 문자열은 서로 겹쳐서 나타나도 무방하다. 예를 들어 비문이 aaaa인 경우, aaa는 0번 인덱스와 1번 인덱스에서 시작하여 서로 겹치지만 두 번 나타난 것으로 인정되므로, 가장 긴 길이는 3이 된다.

비문의 길이 \(N\)과 비문 문자열 \(S\)가 주어질 때, 최소 두 번 이상 등장하는 가장 긴 부분 문자열의 길이를 구하는 프로그램을 작성하시오.

\(1 \le N \le 200\,000\)

문자열 \(S\)는 알파벳 소문자로만 이루어져 있다.

첫째 줄에 비문의 길이 \(N\)이 주어진다 (\(1 \le N \le 200\,000\)). 둘째 줄에 알파벳 소문자로만 이루어진 길이 \(N\)의 비문 문자열 \(S\)가 주어진다. 공백은 포함되지 않는다.

첫째 줄에 최소 두 번 이상 등장하는 가장 긴 부분 문자열의 길이를 출력한다. 만약 두 번 이상 등장하는 부분 문자열이 전혀 없다면 0을 출력한다.

riseoj 작성

출처 Online Judge > GoldOJ