반복 패턴

• 반복패턴의 모든 후보를 찾는 것은 모든 Border을 찾는 것과 동일하고, 이것은 fail함수나 z배열을 이용해서 O(N)에 구할수 있다.
  • 반복 찾기 참고
  • fail 함수를 쓰는것이 z배열을 쓰는 것보다 좀더 빠르다
• 각각의 반복패턴의 후보 P에 대해서, K개 이하의 문자를 덧붙여서 문자열을 반복형태로 변환할수 있는지를 체크해주면 된다. 즉, 덧붙여야 할 최소 문자열의 길이 x = -N % len(P) 를 계산해서, x≤K 인지 확인하면 된다. 답은 조건을 만족하는 가장 긴 P의 길이가 된다.
• K가 N이상인 경우는 따로 예외처리를 해줘야 한다. 원래 문자열 전체를 한번 더 이어붙여서, 원래 문자열 전체를 반복패턴으로 사용하는 것이 가능하기 때문이다.
• 총 시간복잡도는 O(N)

"""Solution code for "BOJ 16229. 반복 패턴".

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

Tags: [KMP algorithm]
"""

from teflib import string as tstring


def main():
    N, K = [int(x) for x in input().split()]
    S = input()

    if K >= N:
        print(N)
        return

    fail = tstring.failure_table(S)
    answer = 0
    border_len = fail[-1]
    while border_len:
        if -N % (N - border_len) <= K:
            answer = N - border_len
        border_len = fail[border_len - 1]
    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.string.failure_table

"""Solution code for "BOJ 16229. 반복 패턴".

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

Tags: [Z algorithm]
"""


from teflib import string as tstring


def main():
    N, K = [int(x) for x in input().split()]
    S = input()

    if K >= N:
        print(N)
        return

    z = tstring.z_array(S)
    z[0] = 0
    for i, z_i in enumerate(reversed(z), start=1):
        if i == z_i and -N % (N - i) <= K:
            print(N - i)
            break
    else:
        print('0')


if __name__ == '__main__':
    main()

• Dependency: teflib.string.z_array