aoj 0538 - IOIOI

問題

問題概要

該当する文字列がいくつ存在するか求める問題。

解法

与えれた文字列(s)にIOIOI等の文字列があるかを調べる。sの先頭から調べていき、Iの文字であれば、その位置から、2*n + 1文字を切り取り、該当する文字(ans)と一致するからを調べている。多分計算量は(m) ?? substrがどのくらいかかるのか分からない。

ミス

計算量がよくわからない。substrはＯ(1)と考えていいのかな？

コード

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

int main(void){
    while(1){
        int n, m; cin >> n;
        if(n == 0) return 0;
        cin >> m;
        string s; cin >> s;
        string ans;
        rep(i, n) ans += "IO";
        ans += "I";
        int sum = 0;
        for (int i = 0; i < m; ++i){
            if(s[i] != 'I') continue;
            if(ans == s.substr(i, 2 * n + 1))
                sum++;
        }
        printf("%d\n", sum);
    }
}