잘못된 커닝
면접 대비시간 제한2초메모리 제한512 MB
공백 사이를 알파벳으로 채워서 접시에 나타나는 긴 문자열에서 원본 S의 가장 긴 접두사가 부분 문자열로 나오게 하고 그 길이를 출력합니다.
문제
여러분과 동료들은 프로그래머에게 이름판을 파는 스타트업을 막 세웠다. 목표 시장을 면밀히 조사한 결과, 고정폭 글꼴을 쓰는 것이 가장 좋다는 결론을 내렸다.
첫 고객이 원본 문자열 S를 이름판에 인쇄해 달라고 요청했다. 그런데 레이저 프린터를 잘못 설정하는 바람에 문자열의 첫 글자 앞, 마지막 글자 뒤, 그리고 모든 글자 사이에 실수로 공백이 하나씩 찍혔다.
고객은 이 이름판을 곧(정확히는 5시간 뒤에) 기다리고 있어서, 프린터를 다시 설정하거나 새 판을 구할 시간이 없다. 지금 판을 살리기로 하고, 프린터로 각 공백에 글자 하나씩을 채워 넣어 원본 문자열 S의 가장 긴 접두사가 판에서 부분 문자열로 나타나게 하려 한다. 부분 문자열이란 연속한 글자열을 말한다.
예를 들어 ENDED를 인쇄하려 했다고 하자. 그런데 프린터는 _E_N_D_E_D_를 인쇄했고(_는 공백), 여기에 JEJNJDJENDE를 채울 수 있다. 이 문자열에는 S의 접두사인 ENDE가 들어 있고, 길이는 4이다. 이것이 가능한 최선이다.
두 번째 예로 문자열 ERROR를 보자. 이것은 _E_R_R_O_R_로 인쇄되고, 여기에 JEJRERRORRJ를 채울 수 있다. 이 경우 원본 문자열 ERROR 전체가 최종 판의 부분 문자열이다.
이름판에 인쇄할 수 있는 원본 문자열의 가장 긴 접두사의 길이는 얼마인가?
입력
입력은 문자열 S가 들어 있는 한 줄로 이루어진다. 문자열은 알파벳 대문자로만 이루어지며 길이는 1 이상 2 000 000 이하이다.
출력
이름판에 인쇄할 수 있는 S의 가장 긴 접두사의 길이를 출력한다.