[Python 3] BOJ - 1305 "광고"

 # 문제 링크 : https://www.acmicpc.net/problem/1305

1305번: 광고

 # 풀이 :

개인적으로 이 문제의 핵심은 KMP알고리즘의 failure 함수의 이해라고 생각한다.

<그림 1. 'aab', 'aba', 'aaa'>

 위 그림1에서는 각기 다른 패턴을 보여준다. 첫번째 패턴인 aab의 경우 가장 짧은 광고가 될 수 있는 경우는 aabaabaab...이다. 즉, 패턴이 그대로 반복되는 것이다. 두번째 패턴인 aba의 경우 정답은 ababab...이다. 이 경우 첫번째 패턴처럼 패턴이 그대로 반복되는 것이 아니다. 세번째 패턴인 aaa의 경우 가장 짧은 광고가 될 수 있는 경우는 aaaaaaa....이다. 이 경우도 두번째 패턴과 마찬가지로 패턴이 그대로 반복되는 경우가 아니다. 

 각 패턴의 failure 함수를 각각 F1, F2, F3라고 하자. 현재 F1의 경우 마지막 세번째 글자의 값이 0이다. 따라서 최대 접미사의 길이가 마지막 글자에서 0임을 알 수 있다. F2의 경우는 1, F3의 경우는 2이다. 왜 마지막 글자의 F값을 살펴야 하는가? 왜냐하면 문제에서 가장 짧은 길이를 구하라고 명시하였기 때문이다.

 따라서, 마지막 문자와 처음으로 다른 글자가 시작되는 위치에서 마지막 글자까지만 반복하면 최단 길이 광고문자열을 구할 수 있다. F1의 경우 마지막 문자인 b와 처음으로 다른 글자가 시작되는 위치는 인덱스 0이므로 마지막 글자와 다른 문자의 갯수는 3 - 0 - 1 = 2(a가 2개)이다. F2의 경우는 마지막 문자인 a와 처음으로 다른 글자가 시작되는 위치는 인덱스 1이므로 마지막 문자와 다른 문자의 갯수는 3 - 1 - 1 = 1(b가 1개)이다. F3의 경우는 0(전부 a)이다. 

 그런데, 광고 문자열에는 마지막 문제도 포함되어야 하므로 문자 하나가 추가되어야 한다. 따라서 마지막 문자와 다른 문자 갯수는 n - F[n - 1] - 1이고, 마지막 문자 하나가 추가되어야 완전한 광고 문자열이 성립하므로 정답은 n - F[n - 1]이다.

 

 # 코드

import sys

# failure : 본문에서 F배열을 리턴하는 함수
def failure(pattern):
    table = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        while j > 0 and pattern[i] != pattern[j]:
            j = table[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
    return table

# 입력 및 정답 출력
n = int(sys.stdin.readline())
pat = sys.stdin.readline().rstrip()
print(n - failure(pat)[n - 1])