두 문자열 \(S\) 와 \(T\) 가 주어진다. \(T\) 가 \(S\) 를 회전(cyclic rotation) 시켜 만들 수 있는 문자열인지 판정하여라.

\(S\) 를 어떤 위치 \(r\) 에서 잘라 앞뒤를 바꾼 \(S_{r+1}\dots S_{|S|} S_1 \dots S_r\) 이 \(T\) 와 같으면 \(T\) 는 \(S\) 의 회전이다. (두 문자열의 길이가 다르면 당연히 회전일 수 없다.)

표준 기법은 \(S\) 를 두 번 이어 붙인 \(S+S\) 안에서 \(T\) 를 KMP로 찾는 것이다. 길이가 매우 크므로 \(O(|S|+|T|)\) 알고리즘이 필요하다.

\(1 \le |S|, |T| \le 1{,}000{,}000\)

\(S\), \(T\) 는 알파벳 소문자로만 이루어져 있다.

첫째 줄에 문자열 \(S\), 둘째 줄에 문자열 \(T\) 가 주어진다.

\(T\) 가 \(S\) 의 회전이면 YES, 아니면 NO 를 출력한다.

riseoj 작성

출처 Original