문제
n+1 개의 I와 n 개의 O를 번갈아 가며 나열한 문자열을 Pn 이라고 하자. 아래 예들을 보자.
P1 = IOI
P2 = IOIOI
P3 = IOIOIOI
...
Pn = IOIOIOIO ... OIOI (I가 n+1개, O가 n개)
정수 n 과 I 와 O 로만 이루어진 문자열 S 가 주어질 때 S 에 Pn 이 몇 군데 포함되어 있는지 출력하는 프로그램을 작성하시오.
입력
첫 행에 n을 나타내는 정수가 입력된다. (1 ≤ n ≤ 1,000,000) 두 번째 행에 문자열 S 의 길이를 나타내는 정수 m이 주어진다. (2*n +1 ≤ m ≤ 1,000,000) 세 번째 행에 I와 O로만 이루어진 문자열 S 가 주어진다.
출력
문자열 S 에 Pn 이 몇 군데 포함되어 있는지 출력하는 프로그램을 작성하시오. S 에 Pn이 포함되지 않는 경우 0을 출력한다.
예제 #1
1
13
OOIOIOIOIIOII
4
예제 #2
2
13
OOIOIOIOIIOII
2
출처
JOI 2009
로그인해야 코드를 작성할 수 있어요.