회문은 앞뒤를 바꾸어 읽어도 같은 연속 부분 문자열이다. 문자열 ABBAA에는 길이 3의 회문이 없으므로 길이 3 이상 회문도 없다는 판단은 맞을까? 더 나아가 길이 5와 6의 회문이 모두 없는 문자열에는 길이 5 이상 회문이 없음을 설명하라.
세 개의 길이 3 부분은 어느 것도 회문이 아니다. 하지만 처음 네 글자 ABBA는 회문이다. 긴 회문 안에서 가운데 세 글자만 찾으려는 검사는 짝수 길이를 놓친다.
회문의 양 끝 글자를 하나씩 지우면 가운데도 회문이다. 이때 길이는 2씩 줄어 홀수·짝수가 바뀌지 않는다. 따라서 길이 5 이상인 홀수 회문은 길이 5로, 길이 6 이상인 짝수 회문은 길이 6으로 줄일 수 있다.
대우로 말하면 길이 5와 6을 모두 검사해 없음을 확인했을 때 더 긴 회문도 없다. 이 검사는 길이 4 회문까지 금지하지 않는다. 무엇을 보장하려는지 먼저 적어야 검사 길이가 정해진다.
교사는 문자열 전체가 회문인지와 그 안의 연속 부분이 회문인지를 구별해 묻는다. 긴 대상의 부재를 작은 검사로 인증하는 이유가 반복 횟수가 아니라 양끝 제거와 홀짝 보존이라는 점을 설명하게 한다.
착안 원문: NZMO 2025 Round 1, Problem 4. 위 조건·문항과 해설은 새로 구성했다. 원문의 문항이나 그림을 번역·재사용한 것이 아니다.