1305번: 광고 / platinum 4 / KMP

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

1305번: 광고

'''
1305번: 광고 / platinum 4 / KMP
'''
# 광고판의 길이 L, 광고판 문자열 board 입력 받기
L = int(input())
board = input()
# pi 리스트 만들기
pi = [0 for _ in range(L)]
j = 0
for i in range(1, L):
    while j > 0 and board[i] != board[j]:
        j = pi[j - 1]
    if board[i] == board[j]:
        j += 1
        pi[i] = j
# 실제 광고 길이 출력하기
print(L - pi[-1])

 

코드 리뷰

- KMP 알고리즘을 더 풀고싶어 해당 문제를 선택 했습니다! (알고리즘 알고 문제 접근)

 

- 해당 문제를 요약하자면, 실제 광고 문자열이 될 수 있는 길이의 최솟값 구하는 문제입니다!

- 즉, '세준이가 순간 본 광고판의 문자열' 을 보고, '실제 광고 문자열'의 길이를 추측해야 합니다.

 

- '세준이가 순간 본 광고판의 문자열'에는 '실제 광고 문자열'이 존재합니다.

- https://ronlee.tistory.com/200 어제 풀은 해당 문제를 활용해 생각해보면,

- '세준이가 순간 본 광고판의 문자열'이 '실제 광고 문자열'을 계속 붙인 것이므로

- '세준이가 순간 본 광고판의 문자열'에서 접두사와 접미사가 같은 최대 길이가 '실제 광고 문자열'의 최소 길이