題意：
模板包括3種字符：
a-z：標準字符
通配符?，代表任意一個字符
*：代表0個或多個字符
先給出n個模板串，m個字符串，問每個字符串分別匹配那幾個模板串
n<=1e6,m<=1e2，strlen<20
解法：
用trie樹構建模板串，然后再dfs來匹配
應為模板串中有重復串，一個簡單的方法是，開辟一個鏈表空間，鏈接每個模板串的末節(jié)點
然后判斷每個字符串時DFS一次，將能到達的尾部節(jié)點做個標記，然后根據(jù)之前記錄的鏈表掃一遍就知道到達過哪些模板串的根節(jié)點（匹配了哪些模板串）
DFS的時候要注意下幾點：
1、狀態(tài)設定：(節(jié)點編號、當前字符串位置)
2、如果當前節(jié)點中存在'?"的轉移路徑，則轉移過去
3、如果當前節(jié)點存在'*'的轉移路徑，枚舉*匹配的長度，然后轉移
總復雜度1e7左右。。。不知道有什么好的方法，我的程序C++跑了400MS。。。不算快的。。
另外，這題建議用動態(tài)內存分配，我開始開了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