> 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感谢路上不知道你过了没，我就是错在你给的第二组数据上！ (0) wuaicr 2010-11-13 22:40:33