Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

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);
	}
}