백준: 1305 광고

문제

1305번: 광고

 

문제 풀이

  전광판에 N개의 문자열을 광고를 표시한다. 이때 시간이 지남에 따라 문자열은 한 칸씩 옆으로 이동한다. 어느 순간 광고판을 볼 때, 쓰여 있는 문자가 입력으로 주어진다면 가능한 광고의 길이 중 가장 짧은 것을 출력하는 문제이다. 이는 `KMP 알고리즘`에서 접미사와 접두사가 되는 문자열의 최대 길이를 생성하면 쉽게 해결할 수 있는 문제이다. 만약 `KMP 알고리즘`에 대해 이해하고 있지 않다면 문제를 풀 수 없다.

 

코드

def make_table(patten):
    table = [0] * l
    j = 0
    for i in range(1, l):
        while j > 0 and patten[i] != patten[j]:
            j = table[j - 1]
        if patten[i] == patten[j]:
            j += 1
            table[i] = j
    return l - table[l - 1]


if __name__ == "__main__":
    l = int(input())
    s = input()
    print(make_table(s))