0538-IOIOI
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0538
Boyer-Mooreのアルゴリズムを用いて数え上げ。
規則性を使えばもっと早くなりそうだけど…。
#include <cstring> #include<cstdio> using namespace std; char strs[1000002]; char mkh[1000002]; int n,m,r,c,t; int main() { for(;~scanf("%d%d",&n,&m);){ if(n==0) break; scanf("%s",strs); mkh[0]='I'; c=0;r=2*n+1; for(int i=0;i<n;i++){ mkh[i*2+1]='O'; mkh[i*2+2]='I'; } for(int i=r-1;i<m;){ if(strs[i]=='I'){ t=0; int j; for(j=0;j<r;j++){ if(strs[i-r+j+1]!=mkh[j]){ if(strs[i-r+j+1]!='I'&&strs[i-r+j+1]!='O'){i+=j-2;} t=1;break; } } if(t==0) {c++;i+=2;} if(t!=0) {i+=2;} }else if(strs[i]=='O'){ i++; } else{ i+=r; } } printf("%d\n",c); } return 0; }