我错了QAQ，前两天刚立下的flag就倒了
AC自动机其实可以做Trie图做不了的题：
比如这道：
2754: [SCOI2012]喵星球上的点名
字符集太大构建不了Trie图。
所以还是老老实实地学习一下AC自动机吧
主要是不管空节点，构建fail指针时一个一个往上蹦直到合法。
匹配也一样。
代码：
1 #include<queue> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using std::queue; 6 struct trnt{ 7 int ch[26]; 8 int fl; 9 int fin; 10 bool vis; 11 }tr[2000000]; 12 char tmp[2000000]; 13 int n; 14 int siz; 15 queue<int>Q; 16 void Insert(char *a) 17 { 18 int len=strlen(a+1); 19 int root=0; 20 for(int i=1;i<=len;i++) 21 { 22 int c=a[i]-\'a\'; 23 if(!tr[root].ch[c]) 24 tr[root].ch[c]=++siz; 25 root=tr[root].ch[c]; 26 } 27 tr[root].fin++; 28 return ; 29 } 30 void Build(void) 31 { 32 int root=0; 33 for(int i=0;i<26;i++) 34 if(tr[root].ch[i]) 35 Q.push(tr[root].ch[i]); 36 while(!Q.empty()) 37 { 38 root=Q.front(); 39 Q.pop(); 40 for(int i=0;i<26;i++) 41 { 42 if(tr[root].ch[i]) 43 { 44 int nxt=tr[root].fl; 45 while(nxt&&!tr[nxt].ch[i]) 46 nxt=tr[nxt].fl; 47 if(tr[nxt].ch[i]) 48 nxt=tr[nxt].ch[i]; 49 tr[tr[root].ch[i]].fl=nxt; 50 Q.push(tr[root].ch[i]); 51 } 52 } 53 } 54 return ; 55 } 56 int Cal(char *a) 57 { 58 int len=strlen(a+1); 59 int root=0; 60 int ans=0; 61 for(int i=1;i<=len;i++) 62 { 63 int c=a[i]-\'a\'; 64 while(root&&!tr[root].ch[c]) 65 root=tr[root].fl; 66 if(tr[root].ch[c]) 67 { 68 root=tr[root].ch[c]; 69 int nxt=root; 70 while(nxt&&!tr[nxt].vis) 71 { 72 ans+=tr[nxt].fin; 73 tr[nxt].vis=true; 74 nxt=tr[nxt].fl; 75 } 76 } 77 } 78 return ans; 79 } 80 int main() 81 { 82 scanf("%d",&n); 83 for(int i=1;i<=n;i++) 84 { 85 scanf("%s",tmp+1); 86 Insert(tmp); 87 } 88 Build(); 89 scanf("%s",tmp+1); 90 printf("%d\n",Cal(tmp)); 91 return 0; 92 }