암호 키
시간 제한2초메모리 제한1024 MB
소문자로 이루어진 길이 500000 이하의 문자열 s가 주어집니다. 각 부분 문자열 t에 대해 |t| + f(t)^2의 최댓값을 구합니다. f(t)는 t의 진접두사이자 진접미사인 가장 긴 문자열의 길이입니다.
문제
에르퀼 푸아로는 지금 미술품 밀수를 일삼는 국제 범죄 조직을 적발하고 있다. 푸아로와 협력하는 경찰이 곧 열릴 거래의 장소와 시간이 적힌 암호화된 편지를 가로챘다. 조직의 우두머리도 이 거래에 참석한다. 거래를 무산시키고 우두머리를 체포하려면 가로챈 편지를 해독해야 한다.
에르퀼은 암호의 키가 문자열 로부터 계산된다는 것을 알고 있다. 문자열 에 대해 를 와 같지 않으면서 의 접두사이기도 한 의 접미사 중 가장 긴 것의 길이로 정의하자. 예를 들어 , , 이다. 키는 의 모든 부분 문자열 에 대한 의 최댓값이다. 에르퀼이 키를 계산하도록 도와주자.
입력
첫 줄에 문자열 가 주어진다. 는 소문자 라틴 알파벳으로만 이루어져 있다. ()
출력
암호의 키인 정수 하나를 출력한다.