[C++] 알고스팟/문자열 검색 - Jaeha's Safe

문제 링크

https://algospot.com/judge/problem/read/JAEHASAFE

algospot.com :: JAEHASAFE

 

현재 상태에서 타겟 상태로 가는 길이를 환형 시프트로 구현해야되는데

이를 kmp 알고리즘으로 간단히 구할 수 있습니다.

 

먼저 아래와 같은 예시에서 시계방향으로 가는 경우 타겟을 두 번 이어붙여서 kmp 알고리즘을 실행하면 이동 횟수를 구할 수 있습니다.

 

반시계방향인 경우 현재 상태를 두 번 이어붙여서 kmp 알고리즘을 실행시키면 마찬가지로 이동 횟수를 구할 수 있습니다.

 

 

구현 코드