3 2
b?g*
b?g*
?ft??
bags
wftke

5 2
t*h*wm
?h*s*w
*h*w
*m*w
*j*j
jj
jjj


5 4
t*
?h*s
??e*
*s
?*e
this
the
an
is

代码如下：
// 1816_WildWord2.cpp : 定义控制台应用程序的入口点。
//

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;


int dict[20000][28];
vector<int> ids[20000];
int isleaf[20000];
int pos=0;

void Insert(string str,int order){
	int len=str.length();
	const char * strchar=str.c_str();
	int tpos=0;
	for(int i=0;i<len;i++){
		char letter=strchar[i];
		if(i==len-1){
			if(letter=='*'){
				
				if(dict[tpos][27]==0){
					dict[tpos][27]=++pos;
					isleaf[tpos]=0;
					
				}
				ids[dict[tpos][27]].push_back(order);
				tpos=dict[tpos][27];
				
			}
			else if(letter=='?'){

				
				if(dict[tpos][26]==0){
					dict[tpos][26]=++pos;
					isleaf[tpos]=0;
				}
				ids[dict[tpos][26]].push_back(order);
				tpos=dict[tpos][26];
				
			}
			else {
				

				if(dict[tpos][letter-'a']==0){
					dict[tpos][letter-'a']=++pos;
					isleaf[tpos]=0;
				}
				ids[dict[tpos][letter-'a']].push_back(order);
				tpos=dict[tpos][letter-'a'];
				
			}
		}
		else{
			if(letter=='*'){
				
				if(dict[tpos][27]==0){
					dict[tpos][27]=++pos;
					isleaf[tpos]=0;
					
				}
				
				tpos=dict[tpos][27];
				
			}
			else if(letter=='?'){

				
				if(dict[tpos][26]==0){
					dict[tpos][26]=++pos;
					isleaf[tpos]=0;
				}
				tpos=dict[tpos][26];
				
			}
			else {
				

				if(dict[tpos][letter-'a']==0){
					dict[tpos][letter-'a']=++pos;
					isleaf[tpos]=0;
				}
				tpos=dict[tpos][letter-'a'];
				
			}
		}
	}
}



void DFS(int ps,string strw,vector<int> & tpv,int order){
	int len=strw.length();
	const char * strwchar=strw.c_str();
	char letter=strwchar[order];
    
	if(dict[ps][letter-'a']!=0){
		
		if((ids[dict[ps][letter-'a']].size()!=0)&&(order==len-1)){
			int sizej=ids[dict[ps][letter-'a']].size();
			for(int j=0;j<sizej;j++){
				tpv.push_back((ids[dict[ps][letter-'a']])[j]);
			}
		}
		else if(order==len-1){
			int etp=dict[dict[ps][letter-'a']][27];
			while(etp!=0){
				int sizej=ids[etp].size();
				for(int j=0;j<sizej;j++){
					tpv.push_back((ids[etp])[j]);
				}
				etp=dict[etp][27];
			}
			return;
		}
		else if(isleaf[ps]==1){
			return;
		}
		else{
			DFS(dict[ps][letter-'a'],strw,tpv,order+1);
		}
	}

	

	if(dict[ps][26]!=0){
		
		if((ids[dict[ps][26]].size()!=0)&&(order==len-1)){
			int sizej=ids[dict[ps][26]].size();
			for(int j=0;j<sizej;j++){
				tpv.push_back((ids[dict[ps][26]])[j]);
			}
		}
		else if(order==len-1){
			int etp=dict[dict[ps][26]][27];
			while(etp!=0){
				int sizej=ids[etp].size();
				for(int j=0;j<sizej;j++){
					tpv.push_back((ids[etp])[j]);
				}
				etp=dict[etp][27];
			}
			return;
		}
		else if(isleaf[ps]==1){
			return;
		}
		else{
			DFS(dict[ps][26],strw,tpv,order+1);
		}
	}
	
	

	if(dict[ps][27]!=0){
		
		if((ids[dict[ps][27]].size()!=0)&&(order==len-1)){
			int sizej=ids[dict[ps][27]].size();
			for(int j=0;j<sizej;j++){
				tpv.push_back((ids[dict[ps][27]])[j]);
			}
		}
		else if(order==len-1){
			int etp=dict[dict[ps][27]][27];
			while(etp!=0){
				int sizej=ids[etp].size();
				for(int j=0;j<sizej;j++){
					tpv.push_back((ids[etp])[j]);
				}
				etp=dict[etp][27];
			}
			
			DFS(dict[ps][27],strw,tpv,order);
			
		}
		
		else{
			
			
			DFS(dict[ps][27],strw,tpv,order);
			
			for(int j=order;j<len-1;j++){
				
				if(j==len-2){
					if(ids[dict[ps][27]].size()!=0){
						int sizeh=ids[dict[ps][27]].size();
						for(int h=0;h<sizeh;h++){
							tpv.push_back((ids[dict[ps][27]])[h]);
						}
					}
				}
				
				DFS(dict[ps][27],strw,tpv,j+1);
				
			}
		}
	}
}


int main(){
	for(int i=0;i<10005;i++){
		isleaf[i]=1;
		for(int j=0;j<10005;j++){
			dict[i][j]=0;
		}
	}
	int n,m;
	cin>>n>>m;
	string strp,strw;
	
	vector<vector<int> > result;
	for(int i=0;i<n;i++){
		cin>>strp;
		Insert(strp,i);
	}
	for(int i=0;i<m;i++){
		vector<int> tpv;
		cin>>strw;
		DFS(0,strw,tpv,0);
		sort(tpv.begin(),tpv.end());
		tpv.erase(unique(tpv.begin(), tpv.end()), tpv.end());

		result.push_back(tpv);
		
	}
	for(int i=0;i<m;i++){
		vector<int> tempv=result[i];
		int size=tempv.size();
		if(size==0){
			cout<<"Not match"<<endl;
		}
		else {
			for(int j=0;j<size;j++){
				cout<<tempv[j]<<" ";
			}
			cout<<endl;
		}
	}
}

• Re:这些测试数据都过了，但还是WA！郁闷啊，麻烦大家能提供些测试数据，谢谢！ (5094) wuaicr 2010-11-13 22:38:46
  • Re感谢路上不知道你过了没，我就是错在你给的第二组数据上！ (0) wuaicr 2010-11-13 22:40:33
• 我也错在你的第二组数据上了。。这题陷阱还是挺多的 (0) 090609103 2011-09-15 13:39:19