백준 1305 - 광고 (Python)

바로전 문제와 동일하게 KMP 알고리즘의 failure function을 사용하면 됩니다.

전체 코드

import sys

input = sys.stdin.readline

def make_table(p):
    P_SIZE = len(p)
    t = [0] * P_SIZE
    j = 0

    for i in range(1, P_SIZE):
        while j > 0 and p[i] != p[j]:
            j = t[j - 1]
        
        if p[i] == p[j]:
            j += 1
            t[i] = j

    return t[-1]
                
L = int(input())
alpabet = input().replace('\n', '')

print(L - make_table(alpabet))