[Python] 백준 1305번: 광고

https://www.acmicpc.net/problem/1305

1305번: 광고

 

import sys
input = sys.stdin.readline


def getMinPossibleLength(string):
    length = len(string)
    pi = [0]*(length)
    j = 0

    for i in range(1, length):
        while j > 0 and string[i] != string[j]:
            j = pi[j - 1]

        if string[i] == string[j]:
            j += 1
            pi[i] = j

    return L - pi[-1]


if __name__ == '__main__':
    L = int(input())
    screen = str(input().rstrip())

    minPossibleLength = getMinPossibleLength(screen)
    print(minPossibleLength)

 

KMP 알고리즘으로 푼다는 발상을 하는 것이 중요하다. KMP의 getPi() 함수만 짤 수 있으면 곧장 이 문제를 풀 수 있다. 해당 알고리즘에 대해 설명한 글의 링크를 첨부한다.

https://rccode.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-1893%EB%B2%88-%EC%8B%9C%EC%A0%80-%EC%95%94%ED%98%B8

 

결론적으로 말해서, 이 문제의 답은 (광고판의 크기) - pi[-1]이다.

아래의 예시들을 참고하자.

 

보라색 글씨는, prefix와 suffix가 겹치는 것을 의미한다.

 

suffix 부분(파란색 글씨)을 제거하면, 그것이 가장 짧은 반복 문자열이 된다. 이에 따라 L - pi[-1]을 해주는 것으로 우리가 원하는 값을 구할 수 있다.