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