poj1816:http://poj.org/problem?id=1816
题意：给你n个模板串，然后每个串除了字母，还有？或者*，？可以代替任何非空单个字符，*可以替代任何长度任何串，包括空字符串。现在给以一些串，问你这些串在哪些串中出现过。
题解：trie+DFS。首先，把n个字符串放到trie中，注意，这n个串中可能有相同的字符串。然后对于每个要查询的串，从根节点进行DFS搜索，注意一些特殊处理，例如匹配到*或者？的处理。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 500001
using namespace std;
const int cha=;
struct node{
int num;
int count[];//从根到此处是否是关键字,并且记录是多少个关键字的结尾
int next[cha];
}tree[N];
int ans[],top;
int n,m;
void init(node &a,int data){
a.num=;
for(int i=;i<cha;i++)
a.next[i] = -;
}
int k = ;
void insert(char s[],int num){
int p = ;
for(int i=;s[i];i++){
int data = s[i]-'a';
if(s[i]=='?')data=;
if(s[i]=='*')data=;
if(tree[p].next[data]==-){//不存在该结点
init(tree[k],num);
tree[p].next[data] = k;
k++;
}
p = tree[p].next[data];
}
int temp=tree[p].num;
tree[p].num++;
tree[p].count[++temp]=num;
}
void DFS(node p,char *s,int len,int cur){
if(cur==len){
if(p.num){
for(int i=;i<=p.num;i++)
ans[++top]=p.count[i];
}
while(p.next[]>&&tree[p.next[]].num==)
p=tree[p.next[]];
if(p.next[]>&&tree[p.next[]].num>){
int tt=tree[p.next[]].num;
for(int i=;i<=tt;i++)
ans[++top]=tree[p.next[]].count[i];
}
return ;
}
int t=s[cur]-'a';
if(p.next[t]>)
DFS(tree[p.next[t]],s,len,cur+);
if(p.next[]>)
DFS(tree[p.next[]],s,len,cur+);
if(p.next[]>){
int temp=cur;
while(temp<=len){
DFS(tree[p.next[]],s,len,temp);
temp++;
}
}
}
char str[];
int main(){
while(~scanf("%d%d",&n,&m)){
init(tree[],-);
for(int i=;i<=n;i++){
scanf("%s",str);
insert(str,i-);
}
for(int i=;i<=m;i++){
scanf("%s",str);
top=;
DFS(tree[],str,strlen(str),);
sort(ans+,ans+top+);
int tt=unique(ans+,ans+top+)-ans-;
if(tt>){
for(int i=;i<tt;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[tt]);
}
else
printf("Not match\n");
}
}
}