백준 1305번: 광고 (Python)

접근

KMP 알고리즘을 이용하면 쉽게 구할 수 있는 문제였다. KMP 알고리즘을 이용하여 failure funtion table 을 구하고 전광판의 길이에서 table의 가장 마지막 값을 빼주면 답을 구할 수 있었다.

KMP 알고리즘 기본 문제: 2021.06.18 - [코딩/백준 (Python)] - 백준 1786번: 찾기 (Python)

백준 1786번: 찾기 (Python)

코드

import sys


def kmptable(a):
    n = len(a)
    table = [0] * n
    j = 0
    for i in range(1, n):
        while j > 0 and a[i] != a[j]:
            j = table[j - 1]
        if a[i] == a[j]:
            j += 1
            table[i] = j
    return table


l = int(sys.stdin.readline())
n = sys.stdin.readline().rstrip()

print(l - kmptable(n)[-1])

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!