부분문자열 필수 트릭 - doubling cyclic substring trick

24597번: Reversibly Cyclic Strings (acmicpc.net)

 

 

문자열 s의 cyclic substring이라는 것은 s를 rotate했을때 부분문자열 t를 말한다.

 

'fatcat'에서 'atf'는 fatcat에서 왼쪽으로 1칸 rotate하면 atcatf인데 여기에 부분문자열로 있다

 

만약 s의 모든 부분문자열 t에 대하여 t를 뒤집은 것이 s의 cyclic substring이라면 s를 'Internally Reversibly Cyclic'이라고 정의한다.

 

주어진 s가 Internally Reversibly Cyclic인지 판단하는 문제

 

 

어떤 부분 문자열 t가 s의 cyclic substring이라는 것을 어떻게 알 수 있을까?

 

한칸 한칸씩 roate해서 판단해봐야할까?

 

fatcat

tfatcaatfatccatfattcatfaatcatf...

 

이런 문자열을 모두 포함할 수 있는 문자열은 원본 문자열을 이어붙이면 된다

 

fatcatfatcat에 fatcat, tfatca, atfatc, catfat, tcatfa, atcatf가 다 있어

 

어떤 부분문자열 t가  fatcat, tfatca, atfatc, catfat, tcatfa, atcatf 각각에서 부분문자열인지 하나하나 확인하는 것보다

 

t가 fatcatfatcat의 부분문자열인지만 확인하면 된다.

 

 

그러면 fatcatfatcat에서 fatcat의 모든 부분문자열을 뒤집은 문자열이 부분문자열로 존재하는지 확인하면 된다

 

모든 부분문자열을 하나하나 다 확인해서 뒤집은 다음 하나하나 다 확인해봐야할까?

 

모든 부분문자열은 fatcat에 존재하므로 fatcat를 뒤집은 문자열 tactaf가 fatcatfatcat에 존재하는지만 확인하면 충분하다

 

모든 부분문자열을 뒤집은 문자열 t1,t2,t3,...가 tactaf의 부분문자열이므로 

 

tactaf가 fatcatfatcat의 부분문자열이라면..?

 

t1,t2,t3,...도 fatcatfatcat의 부분문자열이다.

 

--------------------------------------------------------------------------------------------------------------------------------------------------

 

1) cyclic substring인지 확인할려면 원본문자열을 한번더 이어붙인 문자열에서 substring인지 체크

 

2) s의 모든 부분문자열이 t의 부분문자열인가? 

 

>> s의 모든 부분문자열은 s의 부분문자열이므로 s가 t의 부분문자열이면 당연히 s의 모든 부분문자열도 t에 들어있다

 

s = input()

t = s[::-1]

s += s

if t in s:
    
    print(1)

else:
    
    print(0)