Danganronpa
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 318 Accepted Submission(s): 176
Problem Description
给你n个A串，m个B串，对每个A串，询问，这些B串们在该A串中一共出现过多少次
Input
样例个数
n m
接下来n个A串
接下来m个B串
Output
如问题描述，对每个A输出...
Sample Input
1
5 6
orz
sto
kirigiri
danganronpa
ooooo
o
kyouko
dangan
ronpa
ooooo
ooooo
Sample Output
1
1
0
3
7
Source
解题：AC自动机自动AC
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 250010; 4 struct trie { 5 int word[26],fail,cnt; 6 void init() { 7 fail = cnt = 0; 8 memset(word,-1,sizeof word); 9 } 10 } dic[maxn]; 11 int tot; 12 char str[1000100]; 13 void insertWord(int root,char *s) { 14 for(int i = 0; s[i]; i++) { 15 int k = s[i]-'a'; 16 if(dic[root].word[k] == -1) { 17 dic[++tot].init(); 18 dic[root].word[k] = tot; 19 } 20 root = dic[root].word[k]; 21 } 22 ++dic[root].cnt; 23 } 24 queue<int>q; 25 void build(int root) { 26 while(!q.empty()) q.pop(); 27 q.push(root); 28 while(!q.empty()) { 29 int u = q.front(); 30 q.pop(); 31 for(int i = 0; i < 26; i++) { 32 if(dic[u].word[i] == -1) continue; 33 if(u == 0) dic[dic[u].word[i]].fail = 0; 34 else { 35 int v = dic[u].fail; 36 while(v && dic[v].word[i] == -1) v = dic[v].fail; 37 if(dic[v].word[i] == -1) dic[dic[u].word[i]].fail = 0; 38 else dic[dic[u].word[i]].fail = dic[v].word[i]; 39 } 40 q.push(dic[u].word[i]); 41 } 42 } 43 } 44 int query(int root,char *s) { 45 int i,ans = 0; 46 for(i = 0; s[i]; i++) { 47 int k = s[i]-'a'; 48 while(root && dic[root].word[k] == -1) 49 root = dic[root].fail; 50 if(dic[root].word[k] != -1) { 51 int v = dic[root].word[k]; 52 while(v) { 53 ans += dic[v].cnt; 54 v = dic[v].fail; 55 } 56 root = dic[root].word[k]; 57 } 58 } 59 return ans; 60 } 61 char FK[100001][10010]; 62 int main() { 63 int n,m,t; 64 scanf("%d",&t); 65 while(t--) { 66 dic[tot = 0].init(); 67 scanf("%d%d",&n,&m); 68 for(int i = 0; i < n; ++i) 69 scanf("%s",FK[i]); 70 while(m--) { 71 scanf("%s",str); 72 insertWord(0,str); 73 } 74 build(0); 75 for(int i = 0; i < n; ++i) 76 printf("%d ",query(0,FK[i])); 77 } 78 return 0; 79 }
这才是AC自动机的正确使用方法，Trie图
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 250010; 4 struct Trie{ 5 int ch[maxn][26],fail[maxn],cnt[maxn],tot; 6 int newnode(){ 7 memset(ch[tot],0,sizeof ch[tot]); 8 fail[tot] = cnt[tot] = 0; 9 return tot++; 10 } 11 void init(){ 12 tot = 0; 13 newnode(); 14 } 15 void insert(char *str,int root = 0){ 16 for(int i = 0; str[i]; ++i){ 17 if(!ch[root][str[i]-'a']) 18 ch[root][str[i]-'a'] = newnode(); 19 root = ch[root][str[i]-'a']; 20 } 21 ++cnt[root]; 22 } 23 void build(int root = 0){ 24 queue<int>q; 25 for(int i = 0; i < 26; ++i) 26 if(ch[root][i]) q.push(ch[root][i]); 27 while(!q.empty()){ 28 root = q.front(); 29 q.pop(); 30 for(int i = 0; i < 26; ++i) 31 if(ch[root][i]){ 32 fail[ch[root][i]] = ch[fail[root]][i]; 33 cnt[ch[root][i]] += cnt[ch[fail[root]][i]]; 34 q.push(ch[root][i]); 35 }else ch[root][i] = ch[fail[root]][i]; 36 } 37 } 38 int query(char *str,int ret = 0,int root = 0){ 39 for(int i = 0; str[i]; ++i){ 40 int x = root = ch[root][str[i]-'a']; 41 ret += cnt[x]; 42 } 43 return ret; 44 } 45 }ac; 46 char FK[100001][10010],str[1000010]; 47 int main(){ 48 int kase,n,m; 49 scanf("%d",&kase); 50 while(kase--){ 51 ac.init(); 52 scanf("%d%d",&n,&m); 53 for(int i = 0; i < n; ++i) 54 scanf("%s",FK[i]); 55 while(m--){ 56 scanf("%s",str); 57 ac.insert(str); 58 } 59 ac.build(); 60 for(int i = 0; i < n; ++i) 61 printf("%d ",ac.query(FK[i])); 62 } 63 return 0; 64 }