Problem:


 IOIOI  

問題

 整数 n (1 ≤ n) に対し, n + 1 個の I と n 個の O を I から始めて交互に並べてできる文字列を Pn とする.ここで I と O はそれぞれ英大文字のアイとオーである.

P1IOI

P2IOIOI

P3IOIOIOI

.

.

.

PnIOIOIO ... OI (O が n 個)

図 1-1 本問で考える文字列 Pn

 整数 n と, I と O のみからなる文字列 s が与えられた時, s の中に Pn が何ヶ所含まれているかを出力するプログラムを作成せよ.

例

 n が 1, s が OOIOIOIOIIOII の場合, P1 は IOI であり,下図 1-2 に示した 4ヶ所に含まれている.よって,出力は 4 である.

OOIOIOIOIIOII

OOIOIOIOIIOII

OOIOIOIOIIOII

OOIOIOIOIIOII

	      

              図 1-2  n が 1, s が OOIOIOIOIIOII の場合の例

n が 2, s が OOIOIOIOIIOII の場合, P2 は IOIOI であり,下図 1-3 に示した 2ヶ所に含まれている.よって,出力は 2 である.

OOIOIOIOIIOII

OOIOIOIOIIOII

	      

              図 1-3  n が 2, s が OOIOIOIOIIOII の場合の例

入力

入力は複数のデータセットからなる．各データセットは以下の形式で与えられる．

 1 行目には整数 n (1 ≤ n ≤ 1000000) が書かれている.

 2 行目には整数 m (1 ≤ m ≤ 1000000) が書かれている. m は s の文字数を表す.

 3 行目には文字列 s が書かれている. s は I と O のみからなる.

 全ての採点用データで, 2n + 1 ≤ m である.採点用データのうち, 配点の 50% 分については, n ≤ 100, m ≤ 10000 を満たす.

n が 0 のとき入力の終了を示す. データセットの数は 10 を超えない．

出力

s に文字列 Pn が何ヶ所含まれるかを表す 1 つの整数を含む 1 行からなる.
 -->
データセットごとに,文字列 s に文字列 Pn が何ヶ所含まれるかを表す 1 つの整数を1 行に出力する. s に Pn が含まれていない場合は,整数として 0 を出力せよ.

入出力例

入力例

1
13
OOIOIOIOIIOII
2
13
OOIOIOIOIIOII
0

出力例

4
2

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
1
13
OOIOIOIOIIOII
2
13
OOIOIOIOIIOII
0


Sample output:
4
2

Submission status: Wrong Answer

Solution code:
from string import find
n = input()
m = input()
s = raw_input()
t = "IOI"
for i in range(n-1):
    t += "OI"
i = ans = 0
while 1:
    tmp = find(s[i:-1], t)
    if tmp < 0: break
    i += tmp + 1
    ans += 1
print ans

Submission status: Wrong Answer

Solution code:
def IOI(n):
	m = "I"
	for _ in xrange(n):
		m += "OI"
		
	return m

while True:
	n = input()
	if n == 0 : break

	n = IOI(n)
	m = input()
	nm = raw_input()
	
	print nm.count(n) + 1

Submission status: Wrong Answer

Solution code:
n, m, s= int(input()), int(input()), input()
ioi= "IOI" if n==3 else "IOI"+"OI"*(n-1)
n= 2*n+1
print(sum(1 for i in range(m-n+1) if s[i:i+n]==ioi))

Submission status: Wrong Answer

Solution code:
i = input()
s = 'IO'*i + 'I'
i = input()
j = 0
ss = raw_input()
c = 0
while j != i:
	if ss[j:len(s)+j] == s:
		c = c + 1
	j = j + 1
print c

Submission status: Time Limit Exceeded

Solution code:
from string import find
while 1:
    n = input()
    if n == 0: break
    m = input()
    s = raw_input()
    t = "IOI"
    for i in range(n-1):
        t += "OI"
    i = ans = 0
    while 1:
        tmp = find(s[i:-1], t)
        if tmp < 0: break
        i += tmp + 1
        ans += 1
    print ans

Submission status: Time Limit Exceeded

Solution code:
while 1:
	n=input()
	if n==0:break
	m=input()
	a=raw_input()
	P="I"+"OI"*n
	l=1+2*n
	c=0
	for i in range(m-l+1):
		if all([a[i+k]==P[k] for k in range(l)]):c+=1
	print c

Submission status: Time Limit Exceeded

Solution code:
while 1:
	n=input()
	if n==0:break
	m=input()
	a=raw_input()
	P="I"+"OI"*n
	l=1+2*n
	c=0
	for i in range(m-l+1):
		for k in range(l):
			if a[i+k]!=P[k]:
				break
		else:c+=1
	print c

Submission status: Accepted

Solution code:
while 1:
    n = input()
    if n == 0: break
    m = input()
    s = raw_input()
    t = "IOI" + "OI"*(n-1)
    t_len = 3 + 2 *(n-1)
    ans = 0
    for i in range(m - t_len + 1):
        if s[i:i+t_len] == t: ans += 1
    print ans

Submission status: Accepted

Solution code:
def IOI(n):
	m = "I"
	for _ in xrange(n):
		m += "OI"
		
	return m

while True:
	n = input()
	if n == 0 : break

	w = IOI(n)
	m = input()
	nm = raw_input()
	
	count = 0
	for i in xrange(len(nm) - 2 * n):
		if nm[i:i+2*n+1] == w : count += 1
		
	print count

Submission status: Accepted

Solution code:
base = 2000003
mask = (1 << 32) - 1

while True:
    n = int(input())
    if not n:
        break
    m = int(input())
    s = [int(c == 'I') for c in input().strip()]
    l = 2 * n + 1

    key, i, t = 0, 0, 1
    while i < l:
        key = (key + t) & mask
        t = (t * base ** 2) & mask
        i += 2

    cnt = 0
    t1 = 1
    for _ in range(l):
        t1 = (t1 * base) & mask
    e = 0
    for i in range(l):
        e = e * base + s[i]
    for i in range(m - l):
        if e == key:
            cnt += 1
        e = (e * base - t1 * s[i] + s[i + l]) & mask
    if e == key:
        cnt += 1

    print(cnt)

Submission status: Accepted

Solution code:
while(1):
    n=int(raw_input())
    if n==0:
        break
    else:
        m=int(raw_input())
        s=[0 if c=='O' else 1 for c in raw_input()]
        startc=0
        cur=0
        cnt=0
        ans=0
        for c in s:
            if startc==0 and c==1:
                startc=1
                cur=1
            elif startc:
                if c!=cur:
                    cnt+=1
                    cur=c
                else:
                    startc=c
                    ans+=max(0,(cnt/2-n)+1)
                    cnt=0
        ans+=max(0,(cnt/2-n)+1)
        print ans

Submission status: Accepted

Solution code:
while True:
    n= int(input())
    if n== 0: break
    m, s= int(input()), input()
    ioi= "IOI" if n==3 else "IOI"+"OI"*(n-1)
    n= 2*n+1
    print(sum(1 for i in range(m-n+1) if s[i:i+n]==ioi))

Submission status: Accepted

Solution code:
while 1:
    n=int(input())
    if n==0:break
    a='I'+'OI'*n
    b,s,c=int(input()),input(),0
    for i in range(b-len(a)):
        if s[i:i+len(a)]==a:c+=1
    print(c)

Submission status: Accepted

Solution code:
while 1:
    n=int(input())
    if n==0:break
    a='I'+'OI'*n
    b,s=int(input()),input()
    print(sum(1 for i in range(b-len(a)) if s[i:i+len(a)]==a))

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n==0: break
    m = int(input())
    s = input()

    ar = [0]*m
    ans = 0
    if m >= 3:
        for i in range(2,m):
            if s[i-2:i+1] == "IOI":
                ar[i] = ar[i-2] + 1
                if ar[i] >= n: ans += 1
    print(ans)

Submission status: Accepted

Solution code:
while True:
    n=int(input())
    if n==0:break
    m=int(input())
    s=input()
    count=0
    req=0
    i=0
    while i<m:
        if s[i]=='I':
            i+=1
            while s[i:i+2]=="OI":
                if req==n-1:count+=1
                else:req+=1
                i+=2
            req=0
        else:i+=1
    print(count)

Submission status: Accepted

Solution code:
while True:
  n = int(input())
  if not n: break
  m = int(input())
  s = input()
  ind = 0
  ans = 0
  while ind < m:
    if s[ind] == "I":
      count = 0
      while ind + 2 < m:
        if s[ind + 1] == "O" and s[ind + 2] == "I":
          count += 1
          ind += 2
        else:
          break
      if count - n + 1 >= 0:
        ans += (count - n + 1)
    ind += 1
  print(ans)

Submission status: Accepted

Solution code:
def solve():
  while True:
    n = int(input())
    if not n: break
    m = int(input())
    s = input()
    ind = 0
    ans = 0
    while ind < m:
      if s[ind] == "I":
        count = 0
        while ind + 2 < m:
          if s[ind + 1] == "O" and s[ind + 2] == "I":
            count += 1
            ind += 2
          else:
            break
        if count - n + 1 >= 0:
          ans += (count - n + 1)
      ind += 1
    print(ans)
solve()

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    p = "I" + "OI" * n
    m = int(input())
    s = input()
    c = 0
    i = 0
    while True:
        try:
            i += s[i:].index(p) + 1
            c += 1
        except:
            print(c)
            break

Submission status: Accepted

Solution code:
# AOJ 0538: IOIOI
# Python3 2018.7.1 bal4u

while True:
	n = int(input())
	if n == 0: break
	m = int(input())
	s = input().strip()
	ans = cnt = i = 0
	while i < m:
		if i+1 < m and s[i:i+2] == 'IO':
			cnt += 1
			i += 1
		elif cnt > 0:
			if s[i] == 'O': cnt -= 1
			if cnt >= n: ans += cnt-n+1
			cnt = 0
		i += 1
	print(ans)

Submission status: Accepted

Solution code:
# AOJ 0538: IOIOI
# Python3 2018.7.1 bal4u

import sys
from sys import stdin
input = stdin.readline

while True:
	n = int(input())
	if n == 0: break
	m = int(input())
	s = input().strip()
	ans = cnt = i = 0
	while i < m:
		if i+1 < m and s[i:i+2] == 'IO':
			cnt += 1
			i += 1
		elif cnt > 0:
			if s[i] == 'O': cnt -= 1
			if cnt >= n: ans += cnt-n+1
			cnt = 0
		i += 1
	print(ans)

Submission status: Accepted

Solution code:
while True:
    n = int(raw_input())
    if n == 0:
        break
    m = int(raw_input())

    s = raw_input()

    cache = [0] * m

    for i in xrange(len(s) - 2):
        if s[i:i+3] == 'IOI':
            cache[i + 2] = cache[i] + 1

    print len(filter(lambda x: x >= n, cache))

Submission status: Accepted

Solution code:
from array import array;
while True:
    n = int(raw_input())
    if n == 0:
        break
    m = int(raw_input())

    s = raw_input()

    cache = array('i', (0 for x in xrange(m)))

    for i in xrange(len(s) - 2):
        if s[i:i+3] == 'IOI':
            cache[i + 2] = cache[i] + 1

    print len(filter(lambda x: x >= n, cache))

Submission status: Accepted

Solution code:
from array import array;
while True:
    n = int(raw_input())
    if n == 0:
        break
    m = int(raw_input())

    s = raw_input()

    cache = array('i', (0 for x in xrange(m)))

    for i in xrange(len(s) - 2):
        if s[i:i+3] == 'IOI':
            cache[i + 2] = cache[i] + 1

    print sum(1 for x in cache if x >= n)

Submission status: Accepted

Solution code:
while True:
    try:
        n = input()
        m = input()
        s = raw_input()
        graph = []
        for i in xrange(n):
            graph.append({"I":2*i+1,"O":0})
            graph.append({"I":1,"O":2*(i+1)})
        graph.append({"I":2*n+1,"O":0})
        graph.append({"I":1,"O":2*n})
        cur,score = 0,0
        for c in s:
            cur = graph[cur][c]
            if cur == 2*n+1:
                score += 1
        print score
    except:
        break

Submission status: Accepted

Solution code:
while True:
        n = input()
        if n == 0:
            break
        m = input()
        s = raw_input()
        graph = []
        for i in xrange(n):
            graph.append({"I":2*i+1,"O":0})
            graph.append({"I":1,"O":2*(i+1)})
        graph.append({"I":2*n+1,"O":0})
        graph.append({"I":1,"O":2*n})
        cur,score = 0,0
        for c in s:
            cur = graph[cur][c]
            if cur == 2*n+1:
                score += 1
        print score

Submission status: Accepted

Solution code:
while True:
        n = input()
        if n == 0:
            break
        m = input()
        s = raw_input()
        cur,score = 0,0
        for c in s:
            if cur <= 2*n:
                if cur % 2 == 0:
                    cur = cur+1 if c=="I" else 0
                else:
                    cur = 1 if c=="I" else cur+1
            elif cur == 2*n+1:
                score += 1
                cur = 1 if c=="I" else 2*n
        print score

Submission status: Accepted

Solution code:
while True:
        n = input()
        if n == 0:
            break
        m = input()
        s = raw_input()
        graph = []
        for i in xrange(n):
            graph.append({"I":2*i+1,"O":0,"score":0})
            graph.append({"I":1,"O":2*(i+1),"score":0})
        graph.append({"I":2*n+1,"O":0,"score":0})
        graph.append({"I":1,"O":2*n,"score":1})
        cur,score = 0,0
        for c in s:
            cur = graph[cur][c]
            score += graph[cur]["score"]
        print score

Submission status: Accepted

Solution code:
while True:
    n=input()
    if n==0:break
    m=input()
    s=raw_input()
    Pn="I"+"OI"*n
    cnt,pl=0,len(Pn)
    for i in range(pl,m+1):
        if s[i-pl:i]==Pn:
            cnt+=1
    print cnt

Submission status: Accepted

Solution code:
i = input()
while i != 0:
	s = 'IO'*i + 'I'
	i = input()
	j = 0
	ss = raw_input()
	c = 0
	while j != i:
		if ss[j:len(s)+j] == s:
			c = c + 1
		j = j + 1
	print c
	i = input()

Submission status: Accepted

Solution code:
while 1:
	n=input()
	if n==0:break
	m=input()
	a=raw_input()
	P="I"+"OI"*n
	l=1+2*n
	c=0
	for i in range(m-l+1):
		if a[i:i+l]==P:c+=1
	print c

Submission status: Accepted

Solution code:
while 1:
	n=int(raw_input())
	if n==0:break
	m=int(raw_input())
	a=raw_input()
	P="I"+"OI"*n
	l=1+2*n
	c=0
	for i in range(m-l+1):
		if a[i:i+l]==P:c+=1
	print c

Submission status: Accepted

Solution code:
def main():
    while True:
        n = int(input())
        if n == 0:
            break
        m = int(input())
        s = input()
        pn = "IOI" + ("OI" * (n-1))
        limit = len(pn)
        searchflag = False
        nextI = False
        tmp = []
        start = 0
        i = 0
        ans = 0
        while i < m:
            if searchflag:
                if not nextI and s[i] == "O":
                    nextI = not nextI
                elif nextI and s[i] == "I":
                    nextI = not nextI
                else:
                    if s[i-1] == "I":
                        searching = s[start:i]
                    else:
                        searching = s[start: i - 1]
                    i -= 1
                    if len(searching) >= limit:
                        tmp.append(searching)
                    searchflag = not searchflag
            else:
                if s[i] == "I":
                    start = i
                    nextI = False
                    searchflag = True
            i += 1
        for i in range(len(tmp)):
            ans += len(tmp[i]) // 2 - n + 1
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
while True:
    a = int(input())
    if a == 0:
        break
    word = "IO"*a+"I"
    b = int(input())
    s = input()
    count = 0
    for i in range(b-a*2):
        if word == (s[i:i+a*2+1]):
            count += 1
    print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
IOIOI
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0538

"""
import sys
import re

def solve(n, s):
    ans = 0
    p = '(I(?:OI){' + str(n) + ',})'
    for f in re.findall(p, s):
        repeat = len(f) // 2
        if repeat >= n:
            ans += (repeat - n + 1)
    return ans


def main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        _ = input()
        s = input()
        ans = solve(n, s)
        print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
while 1:
    n=int(input())
    if n==0:break
    m=int(input())
    word=input()
    ans=0
    pick="IO"*n+"I"
    for i in range(m-2*n):
        if word[i:i+2*n+1]==pick:ans+=1
    print(ans)

Submission status: Runtime Error

Solution code:
# AOJ 0538: IOIOI
# Python3 2018.7.1 bal4u

while True:
	n = int(input())
	if n == 0: break
	m = int(input())
	s = input().strip()
	ans, cnt, w, i = 0, 0, len(s), -1
	while i < w:
		i += 1
		if i+1 < w and s[i:i+2] == 'IO':
			cnt += 1
			i += 1
		elif cnt > 0:
			if s[i] == 'O': cnt -= 1
			if cnt >= n: ans += cnt-n+1
			cnt = 0
	print(ans)

Submission status: Runtime Error

Solution code:
while 1:
	n=input()
	if n==0:break
	m=input()
	a=raw_input()
	P="I"+"OI"*n
	l=1+2*n
	c=0
	for i in range(m-l+1):
		for k in range(l):
			if a[i+k]!=P[k]
				break
		else:c+=1
	print c

Submission status: Runtime Error

Solution code:
while 1:
	n=int(raw_input())
	if n==0:break
	m=int(raw_input())
	a=raw_input()
	P="I"+"OI"*n
	l=1+2*n
	c=0
	for i in range(m-l+1):
		if a[i:i+l]=P:
	print c