[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