Z값으로 길이 n 문자열의 반복 블록 후보를 검사할 때 어떤 조건을 적용하나요?

후보 블록 길이를 i라고 하면 n % i == 0과 i+z[i] == n을 함께 확인합니다. 첫 조건은 블록이 전체 길이를 정확히 나누는지, 둘째 조건은 위치 i에서 시작하는 suffix 전체가 문자열 접두와 일치하는지를 뜻합니다. 둘 다 만족하면 앞의 i문자 블록이 정수 번 반복됩니다. 작은 후보부터 검사하면 최소 반복 블록을 얻습니다.

aaaa에서 i=1, z[1]=3이므로 1+3=4이고 4%1=0입니다. 따라서 a가 네 번 반복됩니다. abac에서 i=2는 4%2=0이지만 z[2]=0이라 2+z[2]=2가 4가 되지 않습니다. 나눗셈만으로는 ab와 ac가 다르다는 사실을 잡을 수 없습니다. 반대로 suffix 일치만 보고 나눗셈을 생략하면 마지막에 불완전한 블록이 남을 수 있습니다.

Z의 z[0]은 보통 이 판정에 사용하지 않고 후보는 1부터 봅니다. 문자를 byte로 세는지 code point로 세는지는 n, i, Z의 단위가 모두 같아야 합니다.

두 조건은 서로 다른 실패를 잡습니다. i+z[i]=n은 suffix가 prefix와 끝까지 같다는 뜻이지만 i가 n의 약수가 아니면 마지막 블록이 잘리지 않고 남습니다. 반대로 n%i=0은 블록 경계만 맞춘 것이어서 각 위치의 문자가 같은지는 말해 주지 않습니다. 따라서 코드의 조건식은 n % i == 0 && i + z[i] == n이어야 하며, 후보를 오름차순으로 돌 때 첫 성공이 최소 블록입니다.

예를 들어 abcabcabc는 i=3에서 z[3]=6이고 3+6=9, 9%3=0이므로 abc를 세 번 반복합니다. 반례 abcabca에서는 z[3]=4이고 3+4=7이라 suffix 일치 조건은 만족하지만 7%3=1입니다. 즉 마지막 부분이 완전한 블록이 아니므로 반복으로 판정하면 안 됩니다. Z 조건만으로 충분하다고 하지 말고, 끝까지 같은지와 길이가 정수 개 블록인지 각각 확인해야 합니다.