AOJ 2369 - CatChecker
問題文 : CatChecker
概要 :
文字列$s$ が次のBNF に従っているか判定せよ.
<cat> := "" | 'm' + <cat> + 'e' + <cat> + 'w'
$1 \leqq |s| \leqq 500$
解法 :
まず$1 \leqq |s|$ なのでcat の最小単位は"mew" である.
よって,
・長さが3 以下なら"mew" かどうか比較する.
・そうでなければ先頭と末尾以外で"mew" が連続している部分列を見つけて切り取る を繰り返す
を行いながら判定すれば良い. "mew" を探すのは実質$O(|s|)$ なので$O(|s|^2)$ 時間でこの問題を解ける.
コード :
#include <cstdio> #include <cstring> using namespace std; int main() { char s[1024], t[1024]; scanf("%s", s); while (1){ int len = strlen(s); bool update = false; for (int i = 1; i + 2 <= len - 2; i++){ if (strncmp(&s[i], "mew", 3) == 0){ update = true; int idx = 0; for (int j = 0; j < i; j++){ t[idx++] = s[j]; } for (int j = i + 3; j < len; j++){ t[idx++] = s[j]; } t[idx] = 0; break; } } if (!update){ return (!printf("%s\n", strcmp(s, "mew") ? "Rabbit" : "Cat")); } strcpy(s, t); } }