문제
N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다.
- P1
IOI
- P2
IOIOI
- P3
IOIOIOI
- PN
IOIOI...OI (O가 N개)
I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.
출력
S에 PN이 몇 군데 포함되어 있는지 출력한다.
제한
- 1 ≤ N ≤ 1,000,000
- 2N+1 ≤ M ≤ 1,000,000
- S는
I와 O로만 이루어져 있다.
서브태스크
| 번호 | 배점 | 제한 | | 1 | 50 | N ≤ 100, M ≤ 10 000.
|
| 2 | 50 | 추가적인 제약 조건이 없다.
|
OOIOIOIOIIOIIOOIOIOIOIIOIIOOIOIOIOIIOIIOOIOIOIOIIOII
OOIOIOIOIIOIIOOIOIOIOIIOII
W3sicHJvYmxlbV9pZCI6IjU1MjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJJT0lPSSIsImRlc2NyaXB0aW9uIjoiPHA+TisxXHVhYzFjXHVjNzU4IDxjb2RlPkk8XC9jb2RlPlx1YzY0MCBOXHVhYzFjXHVjNzU4IDxjb2RlPk88XC9jb2RlPlx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTc0LCA8Y29kZT5JPFwvY29kZT5cdWM2NDAgPGNvZGU+TzxcL2NvZGU+XHVjNzc0IFx1YWQ1MFx1YjMwMFx1Yjg1YyBcdWIwOThcdWM2MjRcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFA8c3ViPk48XC9zdWI+XHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5QPHN1Yj4xPFwvc3ViPiA8Y29kZT5JT0k8XC9jb2RlPjxcL2xpPlxyXG5cdDxsaT5QPHN1Yj4yPFwvc3ViPiA8Y29kZT5JT0lPSTxcL2NvZGU+PFwvbGk+XHJcblx0PGxpPlA8c3ViPjM8XC9zdWI+IDxjb2RlPklPSU9JT0k8XC9jb2RlPjxcL2xpPlxyXG5cdDxsaT5QPHN1Yj5OPFwvc3ViPiA8Y29kZT5JT0lPSS4uLk9JPFwvY29kZT4gKDxjb2RlPk88XC9jb2RlPlx1YWMwMCBOXHVhYzFjKTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPjxjb2RlPkk8XC9jb2RlPlx1YzY0MCA8Y29kZT5PPFwvY29kZT5cdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNCBTXHVjNjQwIFx1YzgxNVx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFNcdWM1NDhcdWM1ZDAgUDxzdWI+TjxcL3N1Yj5cdWM3NzQgXHViYTg3IFx1YWQ3MFx1YjM3MCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBTXHVjNzU4IFx1YWUzOFx1Yzc3NCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMCBTXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5TXHVjNWQwIFA8c3ViPk48XC9zdWI+XHVjNzc0IFx1YmE4NyBcdWFkNzBcdWIzNzAgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBOICZsZTsgMSwwMDAsMDAwPFwvbGk+XHJcblx0PGxpPjJOKzEgJmxlOyBNICZsZTsgMSwwMDAsMDAwPFwvbGk+XHJcblx0PGxpPlNcdWIyOTQgPGNvZGU+STxcL2NvZGU+XHVjNjQwIDxjb2RlPk88XC9jb2RlPlx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD5OICZsZTsgMTAwLCBNICZsZTsgMTAgMDAwLjxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+XHVjZDk0XHVhYzAwXHVjODAxXHVjNzc4IFx1YzgxY1x1YzU3ZCBcdWM4NzBcdWFjNzRcdWM3NzQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzEiOiI8dWw+XHJcblx0PGxpPjxjb2RlPk9PPHU+SU9JPFwvdT5PSU9JSU9JSTxcL2NvZGU+PFwvbGk+XHJcblx0PGxpPjxjb2RlPk9PSU88dT5JT0k8XC91Pk9JSU9JSTxcL2NvZGU+PFwvbGk+XHJcblx0PGxpPjxjb2RlPk9PSU9JTzx1PklPSTxcL3U+SU9JSTxcL2NvZGU+PFwvbGk+XHJcblx0PGxpPjxjb2RlPk9PSU9JT0lPSTx1PklPSTxcL3U+STxcL2NvZGU+PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8yIjoiPHVsPlxyXG5cdDxsaT48Y29kZT5PTzx1PklPSU9JPFwvdT5PSUlPSUk8XC9jb2RlPjxcL2xpPlxyXG5cdDxsaT48Y29kZT5PT0lPPHU+SU9JT0k8XC91PklPSUk8XC9jb2RlPjxcL2xpPlxyXG48XC91bD5cclxuIn0seyJwcm9ibGVtX2lkIjoiNTUyNSIsInByb2JsZW1fbGFuZyI6IjIiLCJ0aXRsZSI6IklPSU9JIChJT0lPSSkiLCJkZXNjcmlwdGlvbiI6IjxwPjEgXHU0ZWU1XHU0ZTBhXHUzMDZlXHU2NTc0XHU2NTcwIE4gXHUzMDZiXHU1YmZlXHUzMDU3XHVmZjBjTiArIDEgXHU1MDBiXHUzMDZlIDxjb2RlPkk8XC9jb2RlPiBcdTMwNjggTiBcdTUwMGJcdTMwNmUgPGNvZGU+TzxcL2NvZGU+IFx1MzA5MiA8Y29kZT5JPFwvY29kZT4gXHUzMDRiXHUzMDg5XHU1OWNiXHUzMDgxXHUzMDY2XHU0ZWE0XHU0ZTkyXHUzMDZiXHU0ZTI2XHUzMDc5XHUzMDY2XHUzMDY3XHUzMDRkXHUzMDhiXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDkyIFA8c3ViPk48XC9zdWI+IFx1MzA2OFx1MzA1OVx1MzA4Ylx1ZmYwZVx1MzA1M1x1MzA1M1x1MzA2NyA8Y29kZT5JPFwvY29kZT4gXHUzMDY4IDxjb2RlPk88XC9jb2RlPiBcdTMwNmZcdTMwNWRcdTMwOGNcdTMwNWVcdTMwOGNcdTgyZjFcdTU5MjdcdTY1ODdcdTViNTdcdTMwNmVcdTMwYTJcdTMwYTRcdTMwNjhcdTMwYWFcdTMwZmNcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5QPHN1Yj4xPFwvc3ViPiZuYnNwOzxjb2RlPklPSTxcL2NvZGU+PFwvbGk+XHJcblx0PGxpPlA8c3ViPjI8XC9zdWI+Jm5ic3A7PGNvZGU+SU9JT0k8XC9jb2RlPjxcL2xpPlxyXG5cdDxsaT5QPHN1Yj4zPFwvc3ViPiZuYnNwOzxjb2RlPklPSU9JPFwvY29kZT48XC9saT5cclxuXHQ8bGk+UDxzdWI+TjxcL3N1Yj4mbmJzcDs8Y29kZT5JT0lPSS4uLk9JPFwvY29kZT4gKDxjb2RlPk88XC9jb2RlPiBcdTMwNGMgTiBcdTUwMGIpPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHU2NTc0XHU2NTcwIE4gXHUzMDY4XHVmZjBjSSBcdTMwNjggTyBcdTMwNmVcdTMwN2ZcdTMwNGJcdTMwODlcdTMwNmFcdTMwOGJcdTY1ODdcdTViNTdcdTUyMTcgUyBcdTMwNGNcdTRlMGVcdTMwNDhcdTMwODlcdTMwOGNcdTMwNWZcdTMwNjhcdTMwNGRcdWZmMGNTIFx1MzA2ZVx1NGUyZFx1MzA2YiBQPHN1Yj5OPFwvc3ViPiBcdTMwNGNcdTRmNTVcdTMwZjZcdTYyNDBcdTU0MmJcdTMwN2VcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdTMwNGJcdTMwOTJcdTZjNDJcdTMwODFcdTMwOGJcdTMwZDdcdTMwZWRcdTMwYjBcdTMwZTlcdTMwZTBcdTMwOTJcdTRmNWNcdTYyMTBcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPjxzcGFuIHN0eWxlPVwibGluZS1oZWlnaHQ6MS42ZW1cIj5cdTZhMTlcdTZlOTZcdTUxNjVcdTUyOWJcdTMwNGJcdTMwODlcdTRlZTVcdTRlMGJcdTMwNmVcdTMwYzdcdTMwZmNcdTMwYmZcdTMwOTJcdThhYWRcdTMwN2ZcdThmYmNcdTMwODFcdWZmMGU8XC9zcGFuPjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHU2NTc0XHU2NTcwIE4gXHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvbGk+XHJcblx0PGxpPjIgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHU2NTc0XHU2NTcwIE0gXHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHUzMDUzXHUzMDhjXHUzMDZmXHVmZjBjXHU1MTY1XHU1MjliXHUzMDY4XHUzMDU3XHUzMDY2XHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDhiXHU2NTg3XHU1YjU3XHU1MjE3IFMgXHUzMDZlXHU5NTc3XHUzMDU1XHUzMDRjIE0gXHUzMDY3XHUzMDQyXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDkyXHU4ODY4XHUzMDU5XHVmZjBlPFwvbGk+XHJcblx0PGxpPjMgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHU5NTc3XHUzMDU1IE0gXHUzMDZlXHU2NTg3XHU1YjU3XHU1MjE3IFMgXHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5cdTZhMTlcdTZlOTZcdTUxZmFcdTUyOWJcdTMwNmJcdWZmMGNcdTY1ODdcdTViNTdcdTUyMTcgUyBcdTMwNmJcdTY1ODdcdTViNTdcdTUyMTcgUDxzdWI+TjxcL3N1Yj4gXHUzMDRjXHU0ZjU1XHUzMGY2XHU2MjQwXHU1NDJiXHUzMDdlXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHUzMDRiXHUzMDkyXHU4ODY4XHUzMDU5XHU2NTc0XHU2NTcwXHUzMDkyIDEgXHU4ODRjXHUzMDY3XHU1MWZhXHU1MjliXHUzMDViXHUzMDg4LiBcdTMwODJcdTMwNTcgUyBcdTMwNmIgUDxzdWI+TjxcL3N1Yj5cdTMwNGNcdTU0MmJcdTMwN2VcdTMwOGNcdTMwNjZcdTMwNDRcdTMwNmFcdTMwNDRcdTU4MzRcdTU0MDhcdTMwNmZcdWZmMGMwIFx1MzA5Mlx1NTFmYVx1NTI5Ylx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkphcGFuZXNlIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBOICZsZTsgMSAwMDAgMDAwXHVmZjBlPFwvbGk+XHJcblx0PGxpPjJOICsgMSAmbGU7IE0gJmxlOyAxIDAwMCAwMDBcdWZmMGU8XC9saT5cclxuXHQ8bGk+XHU2NTg3XHU1YjU3XHU1MjE3IFMgXHUzMDZmIDxjb2RlPkk8XC9jb2RlPiBcdTMwNjggPGNvZGU+TzxcL2NvZGU+IFx1MzA2ZVx1MzA3Zlx1MzA0Ylx1MzA4OVx1MzA2YVx1MzA4Ylx1ZmYwZTxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD5OICZsZTsgMTAwLCBNICZsZTsgMTAgMDAwLjxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+XHU4ZmZkXHU1MmEwXHUzMDZlXHU1MjM2XHU5NjUwXHUzMDZmXHUzMDZhXHUzMDQ0XHVmZjBlPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPlA8c3ViPjE8XC9zdWI+IFx1MzA2ZiA8Y29kZT5JT0k8XC9jb2RlPiBcdTMwNjdcdTMwNDJcdTMwOGFcdWZmMGNcdTU2ZjMgMiBcdTMwNmJcdTc5M2FcdTMwNTdcdTMwNWYgNFx1MzBmNlx1NjI0MFx1MzA2Ylx1NTQyYlx1MzA3ZVx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1MzA4OFx1MzA2M1x1MzA2Nlx1ZmYwY1x1NTFmYVx1NTI5Ylx1MzA2ZiA0IFx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjxjb2RlPk9PPHU+SU9JPFwvdT5PSU9JSU9JSTxcL2NvZGU+PFwvbGk+XHJcblx0PGxpPjxjb2RlPk9PSU88dT5JT0k8XC91Pk9JSU9JSTxcL2NvZGU+PFwvbGk+XHJcblx0PGxpPjxjb2RlPk9PSU9JTzx1PklPSTxcL3U+SU9JSTxcL2NvZGU+PFwvbGk+XHJcblx0PGxpPjxjb2RlPk9PSU9JT0lPSTx1PklPSTxcL3U+STxcL2NvZGU+PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHU1NmYzIDIgTiA9IDFcdWZmMGNTIFx1MzA0YyA8Y29kZT5PT0lPSU9JT0lJT0lJPFwvY29kZT4gXHUzMDZlXHU1ODM0XHU1NDA4XHUzMDZlXHU0ZjhiPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPlA8c3ViPjI8XC9zdWI+IFx1MzA2ZiA8Y29kZT5JT0lPSTxcL2NvZGU+IFx1MzA2N1x1MzA0Mlx1MzA4YVx1ZmYwY1x1NTZmMyAzIFx1MzA2Ylx1NzkzYVx1MzA1N1x1MzA1ZiAyXHUzMGY2XHU2MjQwXHUzMDZiXHU1NDJiXHUzMDdlXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHUzMDg4XHUzMDYzXHUzMDY2XHVmZjBjXHU1MWZhXHU1MjliXHUzMDZmIDIgXHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+PGNvZGU+T088dT5JT0lPSTxcL3U+T0lJT0lJPFwvY29kZT48XC9saT5cclxuXHQ8bGk+PGNvZGU+T09JTzx1PklPSU9JPFwvdT5JT0lJPFwvY29kZT48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdTU2ZjMgMyBOID0gMlx1ZmYwY1MgXHUzMDRjIDxjb2RlPk9PSU9JT0lPSUlPSUk8XC9jb2RlPiBcdTMwNmVcdTU4MzRcdTU0MDhcdTMwNmVcdTRmOGI8XC9wPlxyXG4ifV0=