PKU 3098-Frugal Search

問題概要

文字列集合に対して、マッチする辞書順最小の文字列を求める問題。ただしマッチする時に、|で区切られたどれかにマッチすれば良い。
マッチは、+が前に付いた文字を必ず含み、-が前に付いた文字は必ず含まず、さらにそれ以外の一文字以上を含むという条件で行なわれる。

解法

文字列集合を最初にソートし、問題文通りにマッチを実装する

実装(C++)

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector<string> inp;
bool match2(const string &s,const string &q){
	vector<char> unsign,positive,negative;
	for(int i=0;i<(int)q.size();i++){
		if(q[i]=='+'){
			positive.push_back(q[i+1]);
			i++;
		}else if(q[i]=='-'){
			negative.push_back(q[i+1]);
			i++;
		}else{
			unsign.push_back(q[i]);
		}
	}
	bool containUnsigned=false;
	sort(unsign.begin(),unsign.end());
	//最低１つunsignを含むかどうか
	for(int i=0;i<(int)s.size();i++){
		if(binary_search(unsign.begin(),unsign.end(),s[i])){
			containUnsigned=true;
			break;
		}
	}
	if(containUnsigned==false)return false;

	//全てのpositiveを含み、かつnegativeを１つも含まないか
	sort(positive.begin(),positive.end());
	positive.erase(unique(positive.begin(),positive.end()),positive.end());
	sort(negative.begin(),negative.end());
	for(int i=0;i<(int)s.size();i++){
		if(binary_search(negative.begin(),negative.end(),s[i]))return false;
		if(binary_search(positive.begin(),positive.end(),s[i])){
			positive.erase(lower_bound(positive.begin(),positive.end(),s[i]));
		}
	}
	return positive.empty(); //全てのpositiveを使ったか
}
bool match(const string &s,const string &q){
	if(s=="NONE")return true; //番兵
	string _q="";
	for(int i=0;i<(int)q.size();i++){
		if(q[i]=='|'){
			if(match2(s,_q))return true;
			_q="";
		}else{
			_q.push_back(q[i]);
		}
	}
	return match2(s,_q);
}
int main() {
	while(true){
		string s;
		inp.clear();
		while(true){
			cin>>s;
			if(s=="#")return 0;
			if(s=="*")break;
			inp.push_back(s);
		}
		sort(inp.begin(),inp.end()); //辞書順にする
		inp.push_back("NONE");
		while(true){
			cin>>s;
			if(s=="**")break;
			for(int i=0;i<(int)inp.size();i++){
				if(match(inp[i],s)){
					cout<<inp[i]<<endl;
					break;
				}
			}
		}
		cout<<"$"<<endl;
	}
	return 0;
}