题意：
模板包括3种字符：
a-z：标准字符
通配符?，代表任意一个字符
*：代表0个或多个字符
先给出n个模板串，m个字符串，问每个字符串分别匹配那几个模板串
n<=1e6,m<=1e2，strlen<20
解法：
用trie树构建模板串，然后再dfs来匹配
应为模板串中有重复串，一个简单的方法是，开辟一个链表空间，链接每个模板串的末节点
然后判断每个字符串时DFS一次，将能到达的尾部节点做个标记，然后根据之前记录的链表扫一遍就知道到达过哪些模板串的根节点（匹配了哪些模板串）
DFS的时候要注意下几点：
1、状态设定：(节点编号、当前字符串位置)
2、如果当前节点中存在'?"的转移路径，则转移过去
3、如果当前节点存在'*'的转移路径，枚举*匹配的长度，然后转移
总复杂度1e7左右。。。不知道有什么好的方法，我的程序C++跑了400MS。。。不算快的。。
另外，这题建议用动态内存分配，我开始开了100W的buffer，竟然MLE。。。。
代码：
1
# include <cstdio>
2# include <cstring>
3# include <cstdlib>
4
5using namespace std;
6struct node
7
{
8
node *nxt[28];
9 bool in;
10 node()
11
{
12 memset(nxt,NULL,sizeof(nxt));
13 in=false;
14
}
15
}*ans[100005],head;
16char map[255];
17int c=1;
18node* insert(char *str)
19{
20 node *p=&head;
21 for(int i=0;str[i]!='\0';i++)
22 {
23 if(p->nxt[map[str[i]]]==NULL)
24 p->nxt[map[str[i]]]=new node();
25 p=p->nxt[map[str[i]]];
26 }
27 return p;
28}
29void match(node *p,char *str)
30{
31 if(!p) return;
32 if(*str=='\0')
33 {
34 p->in=true;
35 match(p->nxt[27],str);
36 }
37 else
38 {
39 match(p->nxt[map[*str]],str+1);
40 match(p->nxt[26],str+1);
41 for(int i=0;i<=strlen(str);i++)
42 match(p->nxt[27],str+i);
43 }
44}
45int main()
46{
47 int n,m;
48 for(int i='a';i<='z';i++)
49 map[i]=i-'a';
50 map['?']=26;
51 map['*']=27;
52 scanf("%d%d",&n,&m);
53 for(int i=0;i<n;i++)
54 {
55 char str[10];
56 scanf("%s",str);
57 ans[i]=insert(str);
58 }
59 for(int i=0;i<m;i++)
60 {
61 for(int j=0;j<n;j++) ans[j]->in=false;
62 char str[128];
63 scanf("%s",str);
64 match(&head,str);
65 bool flag=false;
66 for(int j=0;j<n;j++)
67 if(ans[j]->in)
68 {
69 flag=true;
70 printf("%d ",j);
71 }
72 if(flag) printf("\n");
73 else printf("Not match\n");
74 }
75 // system("pause");
76 return 0;
77}
78