Hanbit the Developer
[Python] 백준 1305번: 광고 본문
https://www.acmicpc.net/problem/1305
import sys
input = sys.stdin.readline
def getMinPossibleLength(string):
length = len(string)
pi = [0]*(length)
j = 0
for i in range(1, length):
while j > 0 and string[i] != string[j]:
j = pi[j - 1]
if string[i] == string[j]:
j += 1
pi[i] = j
return L - pi[-1]
if __name__ == '__main__':
L = int(input())
screen = str(input().rstrip())
minPossibleLength = getMinPossibleLength(screen)
print(minPossibleLength)
KMP 알고리즘으로 푼다는 발상을 하는 것이 중요하다. KMP의 getPi() 함수만 짤 수 있으면 곧장 이 문제를 풀 수 있다. 해당 알고리즘에 대해 설명한 글의 링크를 첨부한다.
결론적으로 말해서, 이 문제의 답은 (광고판의 크기) - pi[-1]이다.
아래의 예시들을 참고하자.
suffix 부분(파란색 글씨)을 제거하면, 그것이 가장 짧은 반복 문자열이 된다. 이에 따라 L - pi[-1]을 해주는 것으로 우리가 원하는 값을 구할 수 있다.
'Algorithm > 백준' 카테고리의 다른 글
[Python] 백준 1916번: 최소비용 구하기 (0) | 2021.07.16 |
---|---|
[Python] 백준 1504번: 특정한 최단 경로 (0) | 2021.07.15 |
[Python] 백준 1238번: 파티 (0) | 2021.07.13 |
[Python] 백준 1043번: 거짓말 (0) | 2021.07.12 |
[Python] 백준 1893번: 시저 암호 (0) | 2021.07.12 |