AOJ ICPC CatChecker

解説ACしたので簡単に自分の頭の整理をします。

問題文

文字列が与えられるのでそれが「CAT文字列」かどうか判定してください。CAT文字列は最初空文字で、以下のように再帰的に定義されます。
CAT = 'm'+CAT+'e'+CAT+'w

考えたこと

いや再帰っぽいけどわかんねえ→まあよく考えるとハンバーガーだよね、わかるわかる→は？まずハンバーガーを解けませんが→えーハンバーガー解き直したけど解けない→解法見たけどハンバーガーやるだけじゃん、おわりです。

真面目に

ハンバーガーことD - Christmasのように「再帰的に潜りながら線形探索をする」と解ける。典型が全然身についていないのでとてもつらい。ちなみにこの「再帰的に線形探索」はくるさんが教えてくれた表現です。わりと好き。

コード

#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;

string s;
int ind = 0;

void solve() {
    if (s[ind] != 'm') {
        return;
    }
    ++ind;
    solve();
    if (s[ind] != 'e') {
        return;
    }
    ++ind;
    solve();
    if (s[ind] != 'w') {
        return;
    }
    ++ind;
    return;
}

int main() {
    cin >> s;
    int n = s.length();
    solve();
    if (ind == n) cout << "Cat" << endl;
    else cout << "Rabbit" << endl;
}