14959번: Slot Machines

14959번: Slot Machines - KMP

N개의 수들이 주어질 때, 이 수열은 처음 K개의 원소를 제외하고 주기 P를 갖는다.

이 때, K+P가 최소가 되는, 같다면 P가 최소가 되는 K와 P를 출력하는 문제이다.

주기를 찾는 문제는 KMP에서 광고문제로 설명한 적이 있다.

문자열을  이루고 있는 최소의 주기를 구하는 방법은 문자열의 길이가 S일 때, S - pi[S-1]이다.

이를 이용하려면 먼저 pi배열을 구하여야 한다.

pi[i] = N[...i]의 접미사도 되고 접두사도 되는 문자열의 최대 길이로

주기가 시작되는 부분을 알 수 없으므로 모든 N에 대하여 확인해봐야하므로 시간복잡도가 O(N^2)이다.

그러나 여기서 N개의 수를 뒤집어서 생각한다면 주기의 시작부분은 처음부터가 되게 되며

단 한번의 pi배열을 구하는 과정을 통하여 값을 간단하게 구할 수 있다.

K는 N-(i+1), P는 i+1-p[i]이 되며 이들 중 최소값을 구하여 출력하면 풀 수 있는 문제이다.