백준 10266 시계 사진들 C++

https://www.acmicpc.net/problem/10266

10266번: 시계 사진들

시계의 침만 주어진 두 시계가 시간이 일치할 확률을 구하는 문제입니다. 주의할 점은 침이 일정한 규칙을 가지고 있지 않기 때문에, 1 2 3 4 와 4 2 1 3 은 possible을 가집니다.

 

KMP알고리즘을 이용하여 간단히 구할 수 있습니다. (KMP라는 것을 생각하기 좀 어려웠다... 처음에는 각으로 계산하려했다)

 

우선, 입력값은 0 <= a < 360000 이므로, '0' 만으로 이루어진 360000 길이의 string을 2개 구합니다.

(bool 배열 등을 kmp에 활용하면 더 빠를 것으로 예상. 하지만 전에 string을 기준으로 짰었어서 그냥 string으로 처리했습니다....)

 

그 다음 입력으로 들어오는 위치의 값을 모두 '1'로 바꿉니다. 그리고 첫 번째 입력의 값들로 구성된 string (s1)을 탐색 당하는 string 이라고 했을 때, 시계는 환형으로 동작하므로, s1을 한 번 더 이어 써준다면 탐색하는 string (s2)를 환형으로 처리한 것과 같은 효과를 얻을 수 있습니다.

 

그리하여 760000 길이의 s1에 대해 360000 길이의 s2를 탐색하여 끝까지 가기 전 일치하는 부분이 생기면 possible한 경우입니다. 

 

코드는 다음과 같습니다.