canplane   3년 전

길이 N인 문자열 S와 0 ≤ k < N인 정수 k에 대하여 두 부분 문자열 S[0:k], S[(N - k):N]이 일치한다고 하자.

이는 다시 말해, 0 ≤ i < k인 모든 정수 i에 대하여 S[(N - k) + i] = S[i]이 성립한다는 의미이다. 이를 만족하는 k 중 최댓값을 K라 하자.

그러면 q = N - k에 대하여 q의 최솟값을 Q라 할 때, k의 정의상 0 < N - k ≤ N이므로 q는 자연수이며 Q = N - K이다.

즉, S[q + i]= S[i]를 만족하는 자연수 q의 최솟값은 Q이다.



한편 S가 최소 주기 P를 갖는다는 것은 S의 정의역 내 모든 i에 대하여 S[p + i] = S[i]를 만족하는 자연수 p 중 최솟값이 P임을 의미한다.

이는 Q의 정의와 일치하므로 P = Q = N - K이다.



S[(N - k):N]를 만족하는 정수 k 중 최댓값 K는 KMP 알고리즘에서의 S[0:N]에 대한 fail 값과 같으므로, 

위 논의에 따라 S의 최소 주기는 S의 길이에서 마지막 fail 값을 뺀 값과 동일함을 알 수 있다.

댓글을 작성하려면 로그인해야 합니다.