> IOIOI > Silver I > #[[문자열]] ### 문제 요약 N+1개의 I와 N개의 O로 이루어져 있으며 I, O가 교대로 나오는 문자열을 $P_N$이라고 합시다. I, O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S 안에 $P_N$이 몇 군데 포함되어 있는지 구해야 합니다. N, M의 범위는 100만까지입니다. ### 해설 I, O로만 이루어진 긴 문자열(haystack)에서 특정한 문자열(needle)의 매칭 횟수를 선형 시간에 계산해야 하는 문제입니다. 그러한 문제를 일반적으로 해결하기 위한 여러 알고리즘이 있지만, 그것들을 몰라도 이 문제를 풀 수 있습니다. 문자열을 왼쪽부터 순회하면서 첫 번째로 매칭되는 $P_N$을 찾습니다. 그 다음으로 매칭되는 $P_N$에는 첫 번째로 매칭된 $P_N$과 겹치는 부분이 있을 수도 있는데, 그렇다면 앞으로 다시 돌아가야 할까요? 돌아가는 순간 저희의 방법은 선형 알고리즘이 아니게 되겠죠... 이 문제에서 눈여겨보아야 할 점은, $P_N$에 있는 N+1개의 I는 전부 서로 다른 $P_N$의 시작점이 될 수 있다는 것입니다. 첫 $P_N$에서 두 번째로 나오는 I, 여기서부터 시작하는 $2N+1$ 길이 문자열이 실제로 $P_N$과 동일한지 알려면 맨 뒤 두 자리만 'OI'인지 확인하면 됩니다. 왜냐하면 그 전까지는 이미 $P_{N-1}$과 같다는 사실을 알고 있으니까요! 따라서 실제 구현은 다음과 같이 하면 됩니다. - 'IOI'가 연속으로 몇 번 나왔는지 세면서 `cnt` 변수를 1씩 올립니다. - `cnt >= N`이 되는 순간부터 정답을 1씩 올립니다. ### 배울 점 사실 이 문제는 대표적인 문자열 매칭 알고리즘인 KMP(Knuth-Morris-Pratt)의 아주 직관적인 예제입니다. '이미 본 정보를 버리지 말고, 패턴이 다시 시작되는 지점을 찾아서 순회'하는 KMP의 가장 중요한 아이디어를 이 문제를 공부하면서 맛볼 수 있는 것이죠.