kmjp's blog

競技プログラミング参加記です

DigitalArts プログラミングコンテスト2012 : A - C-Filter

学生向けということで不参加。
その後別途チャレンジしてみた。
難易度は普段のARCより簡単か?3問目がARCのCとDの間位の難易度。

ではまず1問目。
http://digitalarts2012.contest.atcoder.jp/tasks/digitalarts_1

ワイルドカード付で文字列の一致判定を行う。
ただ、ワイルドカードは1文字にしかマッチしないので、「ワイルドカード以外の文字で不一致の場所があれば、文字列全体が不一致」とすればよい。

int S;
char cmd[1001][1001];
char line[1005];
int N;
char ng[100][100];
int ngl[100];

int match(char* st, char* pat) {
	while(*st) {
		if(*pat!='*' && *st !=*pat) return 0;
		pat++;
		st++;
	}
	return 1;
}

void solve() {
	int x,y,i,j;
	char *p;
	int first=1;
	
	S=0;
	while(1) {
		GETs(cmd[S]);
		if(isalpha(cmd[S][0])) {
			S++;
		}
		else {
			N=atoi(cmd[S]);
			break;
		}
	}
	FOR(i,N) {GETs(ng[i]); ngl[i]=strlen(ng[i]);}
	FOR(j,S) {
		if(j) _P(" ");
		
		p=cmd[j];
		FOR(i,N) {
			if(strlen(p) != ngl[i]) continue;
			if(match(p,ng[i])) {
				FOR(x,strlen(p)) _P("*");
				break;
			}
		}
		if(i==N) _P("%s",p);
	}
	_P("\n");
	return;
}

まとめ

マッチング処理自体は問題なかったが、何気に1行の文字をスペースで分割する処理に手こずった。
最初strtok使ったけど使い方を間違えたりとか…。