2018. 1. 27. 18:53, 알고리즘/BOJ
https://www.acmicpc.net/problem/4354
문제에서의 'a'에 해당하는 문자열을 X라고 표시해봅시다. 예를 들어 abcabcabc인 경우 간편하게 XXX로 표현할 수 있습니다. 이 때 전체 문자열을 input으로 하는 KMP의 실패함수를 생각해보면 'XX'가 전치사와 접미사에 자리할 것입니다.
이를 일반화하면 'XXX....X'(X가 n개)에서 전체 문자열을 input으로 하는 KMP의 실패함수는 'XXX...X'(X가 n-1개)이고, 역 또한 귀납적으로 생각해보면 성립합니다. 그러므로 KMP의 실패함수를 구한 후에 이를 가지고 n을 알아낼 수 있습니다.
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 9536번: What does the fox say? (0) | 2018.01.31 |
---|---|
[BOJ] 14889번: 스타트와 링크 (0) | 2018.01.29 |
[BOJ] 5052번: Phone List (0) | 2018.01.27 |
[BOJ] 1701번: Editor (0) | 2018.01.24 |
[BOJ] 3111번: CENZURA (0) | 2018.01.22 |
[BOJ] 14891번: 톱니바퀴 (0) | 2018.01.21 |
Comments