알파벳 소문자로만 이루어진 문자열을 생각해 보자. 접두사란 부분 문자열 중 시작 부분이 가장 앞인 문자열을 의미한다. 접미사란 부분 문자열 중 끝 부분이 가장 뒤인 문자열을 의미한다. 특별히, 빈 문자열은 접두사이면서 접미사이다. 한 문자열의 접두사를 떼어낸 뒤 가장 뒤로 옮기는 것으로 다른 문자열을 만들 수 있다면, 두 문자열은 주기적 동형 관계라고 한다. 예를 들어, ababba와 abbaab는 주기적 동형 관계이나, ababba와 ababab는 아니다. 특별히, 모든 문자열은 자기 자신과 주기적 동형 관계에 있다.

길이 n인 문자열 t가 주어진다. 우리는 이 문자열에서 다음 조건을 만족하는 같은 길이의 접두사 p와 접미사 s를 찾을 것이다.

p와 s는 주기적 동형 관계에 있어야 하며, p와 s의 길이는 n/2을 넘을 수 없고 (p와 s는 t 안에서 겹칠 수 없다), p와 s의 길이의 합은 최대가 되어야 한다.

#3714 upload 5 done 4 how_to_reg 4

Prefixuffix timer 1s memory 128MB

#3714

Prefixuffix 1s 128MB