반응형
https://www.acmicpc.net/problem/1305
1305번: 광고
세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광
www.acmicpc.net
size = int(input())
b = input()
table = [0 for _ in range(len(b))]
i = 0
for j in range(1, len(b)):
while i > 0 and b[i] != b[j]:
i = table[i-1]
if b[i] == b[j]:
i += 1
table[j] = i
print(size-table[-1])초반엔 너무 어렵게 생각해서 감이 안잡혔는데,
파이 배열을 이용하여 pi[-1]을 구하면 끝이었다.
댓글