题意：给出n个模式串，串中除开小写字母外，？代表一个字符，*代表可空的任意字符串，然后再给出m个字符串，问有多少个模式串可以与之匹配。
题解：通过模式串建立字典树，接着就是用字符串去dfs就行了，需要注意的就是遇到当前节点为*则还可以继续走当前结点，由于每次dfs要么字典树匹配深度加1，要么字符串位置加1，所以不会出现死循环。另外这题有些卡内存，模式串可能一样，记录每个结点代表哪些模式串时可以参照图论建边的方法，建一个邻接表储存各个结点的模式串信息。
View Code 1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int N=100005; 8 struct node 9 { 10 char ch; 11 int next[30]; 12 void init(char _ch) 13 { 14 ch=_ch; 15 memset(next,-1,sizeof(next)); 16 } 17 }tr[N*10]; 18 int cnt,head[N],nc; 19 bool mark[N]; 20 struct Edge 21 { 22 int to,next; 23 }edge[N*2]; 24 void add(int a,int b) 25 { 26 edge[nc].to=b;edge[nc].next=head[a];head[a]=nc++; 27 } 28 inline int change(char x) 29 { 30 if(x=='?') 31 return 26; 32 else if(x=='*') 33 return 27; 34 else 35 return x-'a'; 36 } 37 void insert(char s[],int id) 38 { 39 int i,p; 40 for(i=0,p=0;s[i]!='\0';i++) 41 { 42 int pt=change(s[i]); 43 if(tr[p].next[pt]==-1) 44 { 45 tr[p].next[pt]=cnt; 46 p=cnt++; 47 tr[p].init(s[i]); 48 } 49 else 50 p=tr[p].next[pt]; 51 } 52 add(p,id); 53 } 54 bool flag; 55 void dfs(char s[],int p) 56 { 57 if(s[0]=='\0') 58 { 59 for(int i=head[p];i!=-1;i=edge[i].next) 60 flag=mark[edge[i].to]=true; 61 if(tr[p].next[27]!=-1) 62 dfs(s,tr[p].next[27]); 63 return; 64 } 65 int pt=change(s[0]); 66 if(tr[p].next[pt]!=-1) 67 dfs(s+1,tr[p].next[pt]); 68 if(tr[p].next[26]!=-1) 69 dfs(s+1,tr[p].next[26]); 70 if(tr[p].next[27]!=-1) 71 dfs(s+1,tr[p].next[27]),dfs(s,tr[p].next[27]); 72 if(tr[p].ch=='*') 73 dfs(s+1,p); 74 } 75 int main() 76 { 77 int n,m; 78 while(scanf("%d%d",&n,&m)!=EOF) 79 { 80 tr[0].init('$'); 81 cnt=1; 82 memset(head,-1,sizeof(head)); 83 nc=0; 84 for(int i=0;i