Codeforces Round #188 Strings of Power

問題

文字列tが与えられる。tの中に含れる部分文字列のうちheavy*metalにマッチするものの数を求めよ。

解法

heavyにマッチする部分文字列の位置pと、metalにマッチする部分文字列の位置qをあらかじめ求めておく。
その後、(p, q)の組み合わせを求めればよい。

ソースコード

自分で書いたコード。これは無駄がある。heavyにマッチする位置に来たら今いるところより後にあるmetalの個数を足している。これをやるにはある位置より後にあるmetalの個数を前処理で計算しておかないといけない（sumg[]のところ）。

const int L = 1e6;
char t[L+1];
bool f[L], g[L];
int sumg[L+1];

int main() {
    scanf(" %s", t);
    int len = strlen(t);

    for (int i = 0; i < len; i++) {
        if (strncmp("heavy", t+i, 5) == 0)
            f[i] = true;
    }

    for (int i = 0; i < len; i++) {
        if (strncmp("metal", t+i, 5) == 0)
            g[i] = true;
    }

    for (int i = len-1; i >= 0; i--) {
        sumg[i] = sumg[i+1];
        if (g[i])
            sumg[i]++;
    }

    long long ret = 0;
    for (int i = 0; i < len; i++) {
        if (f[i])
            ret += sumg[i];
    }

    cout << ret << endl;
    
    return 0;
}

逆の発想で、metalにマッチする場所に来たら今より前にあるheavyの個数を足す。という風にプログラミングするとシンプルに書ける。

const int L = 1e6;
char t[L+1];
int flg[L];

int main() {
    scanf(" %s", t);
    int len = strlen(t);

    for (int i = 0; i < len; i++) {
        if (strncmp("heavy", t+i, 5) == 0)
            flg[i] = 1;
    }

    for (int i = 0; i < len; i++) {
        if (strncmp("metal", t+i, 5) == 0)
            flg[i] = -1;
    }

    long long ret = 0;
    int cnt = 0;
    for (int i = 0; i < len; i++) {
        if (flg[i] == 1)
            ++cnt;
        else if (flg[i] == -1)
            ret += cnt;
    }

    cout << ret << endl;
    
    return 0;
}