Google Code Jam 2020 Round 1A : A. Pattern Matching

ミスによるタイムロスはあったけど、それ以外は問題なく通過。
https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd74/00000000002b3034

問題

ワイルドカードを含む文字列が複数S[i]が与えられる。
全文字列にマッチする文字列Tを構築せよ。

解法

各文字列S[i]を、最初のアスタリスクの前・最後のアスタリスクの後・それ以外の3パートに分ける。
全S[i]におけるアスタリスクの前のうち、最長のものをPとおく。
その場合、全S[i]におけるアスタリスクの前の部分は、Pのprefixでなければならない。
同様に、全S[i]におけるアスタリスクの後のうち最長のものをQと置くと、全S[i]におけるアスタリスクの後の部分はQのsuffixでなければならない。
まずこれらを確認しよう。

その後、以下のように並べるとよい。余計な部分はアスタリスクが吸収してくれる。
P+(S[0]の「それ以外」の部分)+(S[1]の「それ以外」の部分)+....+Q

int N;
vector<string> V[101];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) {
		string S;
		cin>>S;
		V[i].clear();
		V[i].push_back("");
		FORR(c,S) {
			if(c=='*') {
				V[i].push_back("");
			}
			else {
				V[i].back().push_back(c);
			}
		}
	}
	string pre="",suf="";
	FOR(i,N) {
		if(V[i][0].size()>pre.size()) pre=V[i][0];
		if(V[i].back().size()>suf.size()) suf=V[i].back();
	}
	int ok=1;
	FOR(i,N) {
		if(pre.substr(0,V[i][0].size())!=V[i][0]) ok=0;
		if(suf.substr(suf.size()-V[i].back().size())!=V[i].back()) ok=0;
	}
	
	if(ok==0) {
		_P("Case #%d: *\n",_loop);
	}
	else {
		string T;
		T=pre;
		FOR(i,N) {
			for(j=1;j<V[i].size()-1;j++) T+=V[i][j];
		}
		T+=suf;
		_P("Case #%d: %s\n",_loop,T.c_str());
	}
	
}

まとめ

1AのAの割に難しい？と思ったけどこんなもんか。