문제 1305번: 광고 (acmicpc.net) 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net 해설 KMP 알고리즘을 응용해 풀 수 있는 문제다. KMP 알고리즘은 접두사(postfix)와 접미사(prefix)에 같은 부분이 있으면, 그 정보를 '부분 일치 테이블'(PI) 에 미리 기록해두었다가 다음 탐색 시 활용한다. 예를 들어, 'ABCAB' 라는 문자열의 PI 테이블은 다음과 같이 구할 수 있다. 문자열 A B B A B PI TABLE 0 0 0 1 2 이 문제에서 주목해야 할 점은 전광판이 문자열을 출력하고, 남는 ..