[c++] 코딩인터뷰 완전분석 - 배열과 문자열 8

문제

한 단어가 다른 단어에 포함된 문자열인지 판별하는 isSubstring이라는 메서드가 있다고 하자. s1과 s2의 두 문자열이 주어졌을 때, s2가 s1을 회전시킨 결과인지 판별하는 코드를 isSubstring을 한 번만 호출하도록 하여 작성하라(가령 'waterbottle'은 'erbottlewat'을 회전시켜 얻을 수 있는 문자열이다).

 

풀이

두 문자열에서 s2가 s1을 회전시킨 경우인지를 확인하려면 s1 두 개를 이어붙이고 s2가 이어붙인 s1의 부분 문자열인지를 확인하면 됩니다. 이 문제는 알고스팟의 Jaeha's Safe와 비슷한 문제로 한 문자열을 이어붙이고 다른 문자열이 부분 문자열인지를 kmp 알고리즘으로 확인하면 됩니다.

 

 

구현 코드