====== Slot Machines ======

===== 풀이 =====
  * 수열로 주어지지만, 각 수들을 캐릭터처럼 생각하면 그냥 문자열이나 다름없다. 
  * 그러면, 주어진 문자열을, S = S[:K] + S[K:K+P]*n + S[K:K+m] 과 같은 형태로 표현하겠다는건데.. [[ps:문자열#반복 찾기]] 에서 하던 표현인데 앞에 K개의 문자가 더 추가된 형태이다.
  * K값에 따라서 S[1:]의 반복패턴, S[2:]의 반복패턴.. 을 다 구하는 것은 당연히 좋은 방법이 아니다. 대신 S를 뒤집어서 T를 만들고 T[:-1], T[:-2], ..의 반복패턴을 찾는것은 fail 함수로 바로 가능하다.
  * T에 대해서 fail 함수를 계산하자. 각 T[:-K] 에서 가장 짧은반복문자열의 길이 P=(N-K)-fail[N-K-1]이다. 이항하면 P+K = N-fail[N-K-1]이므로, 이값이 가장 작아지려면 fail함수값이 가장 커져야 한다. 그래서 fail 테이블에서 가장 큰 값을 찾아서 P와 K를 구하면 된다. 가장 큰값이 여러개일때에는 P를 가장 작게 하는것을 찾아야 하는데, 이는 K가 가장 큰것을 찾으면 된다. 이건 다시 N-K가 가장 작은 것이므로, fail table에서 가장 큰 값중에서 가장 앞에있는 것을 찾으면 된다. 그때의 인덱스 i = N-K-1 이므로, K=N-i-1로 구하면 된다. P=N-fail[i]-K 이 된다.
  * 시간복잡도는 failure table을 만드는데 O(n), 최댓값을 찾는데 O(n)이다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 14959. Slot Machines".

- Problem link: https://www.acmicpc.net/problem/14959
- Solution link: http://www.teferi.net/ps/problems/boj/14959

Tags: [KMP]
"""


def failure_table(s):
    """Returns failure table of given string s."""
    fail, j = [0], 0
    for s_i in s[1:]:
        while j > 0 and s_i != s[j]:
            j = fail[j - 1]
        if s_i == s[j]:
            j += 1
        fail.append(j)
    return fail


def main():
    n = int(input())
    nums = input().split()

    fail = failure_table(nums[::-1])
    max_f = max(fail)
    pos = fail.index(max_f)
    k = n - pos - 1
    p = pos + 1 - max_f
    print(k, p)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:플래티넘_3}}