문자열이 반복 블록으로 이루어졌는지 prefix function으로 판단할 때 나눗셈 조건은 무엇인가요?

길이 n인 문자열의 마지막 접두 함수 값을 π[n-1]이라 하면 k=n-π[n-1]를 최소 반복 블록의 후보로 계산합니다. 이때 반드시 n % k == 0인지 확인해야 합니다. 나누어떨어지면 길이 k의 접두 블록이 전체를 반복하고, 아니면 k는 단지 접두와 접미가 겹친 뒤 남은 후보 길이일 뿐 전체 반복 주기가 아닙니다.

ababab에서는 π[5]=4이므로 k=2입니다. 6 % 2=0이고 접두 ab를 세 번 이어 붙인 문자열이므로 반복 블록 길이는 2입니다. 반면 ababa에서도 π[4]=3이라 k=2가 나오지만 5 % 2=1입니다. aba라는 border가 있다고 해서 문자열 전체가 ab의 반복이라고 말할 수 없습니다. 마지막 한 블록이 완전히 채워지지 않기 때문입니다.

이 조건은 최소 후보를 빠르게 얻는 방법이지, 입력 단위나 빈 문자열 정책까지 정해 주지는 않습니다. 빈 문자열은 보통 별도 반환 규칙을 두고, 비ASCII 입력은 π를 계산한 단위와 블록 길이 단위를 동일하게 유지해야 합니다.

왜 k가 후보가 되는지는 마지막 border의 길이를 보면 분명합니다. π[n-1] 길이만큼의 접두와 접미가 같다면, 접미를 시작하는 위치는 n-π[n-1]인 k입니다. n이 k의 배수라면 이 겹침이 한 블록씩 반복되는 경계를 만들고, 더 짧은 블록이 가능했다면 마지막 border가 더 길어져야 하므로 후보도 최소입니다. 반대로 배수가 아니면 겹치는 prefix와 suffix 사이에 남는 부분이 블록 단위로 채워지지 않습니다.

실제 코드에서는 길이 1 문자열이나 빈 문자열을 먼저 처리하는 것이 안전합니다. π[n-1] 접근 전에 n=0을 검사하고, n=1이면 k=1로 반복 여부를 정의합니다. 또한 문자열을 정규화하거나 대소문자를 접는 단계가 있다면 판정 전에 처리해야 합니다. 원본 표시 문자열의 반복 여부와 검색 키의 반복 여부를 섞으면 결과를 재현하기 어렵습니다.