[BOJ] 4354번: Power Strings

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을 알아낼 수 있습니다.


https://github.com/blisstoner/BOJ/blob/master/4354.cpp

'알고리즘 > 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
댓글 쓰기