KMP. [1305]

[1. 문제 설명]

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

---

[2. 풀이 접근]

간단한 방법

• 광고 문구 길이를 1부터 시작해서 반복
• 각 시작 위치부터 광고문구 길이를 n 이라 했을 때, 문자열이 반복되는지 확인해야 함
• 시간복잡도 = O(N³)
• 시간 초과.

kmp 알고리즘 중 부분 매치 테이블을 이용한 풀이

• 핵심은, n 글자 일치 했을 때, 접두사==접미사인 가장 긴 문자열의 길이를 구하는 것
• 자세한 설명은 주석 참조

---

[3. 코드]