[洛谷 3796]【模板】AC自动机(加强版)
Problem:
题目描述
有 个由小写字母组成的模式串以及一个文本串 。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串 中出现的次数最多。
输入输出格式
输入格式:
输入含多组数据。
每组数据的第一行为一个正整数 ,表示共有 个模式串, 。
接下去 行,每行一个长度小于等于 的模式串。下一行是一个长度小于等于 的文本串 。
输入结束标志为 。
输出格式:
对于每组数据,第一行输出模式串最多出现的次数,接下去若干行每行输出一个出现次数最多的模式串,按输入顺序排列。
输入输出样例
输入样例#1:
2 aba bab ababababac 6 beta alpha haha delta dede tata dedeltalphahahahototatalpha 0
输出样例#1:
4 aba 2 alpha haha
Solution:
本题是简单的 AC 自动机应用。关于 AC 自动机请见:AC自动机模板。
由于要查询出现次数最多的模式串,我们可以用 vector 标记 Trie 上每个点结束的模式串,通过统计每个点访问次数算出模式串的出现次数。
注意每组数据处理前统计数组一定要清空,而 Trie 可以在申请新节点时清空该节点以提高效率。
Code: O(L), L为所有串总长 [4496K, 1440MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<queue> using namespace std; int N, times[152]; char P[152][72], T[1000002]; struct Aho_Corasick_Automaton{ int trie[10502][26], fail[10502], topp, cnt[10502]; vector<int> s[10502]; queue<int> q; inline int newNode(){ topp++, memset(trie[topp], 0, sizeof(trie[topp])); return topp; } inline void clear(){ for(register int i = 1; i <= topp; i++) s[i].clear(); topp = -1, newNode(); memset(fail, 0, sizeof(fail)); memset(cnt, 0, sizeof(cnt)); } inline void insert(char *str, int str_id){ int len = strlen(str), cur = 0; for(register int i = 0; i < len; i++){ int v = str[i] - 'a'; if(!trie[cur][v]) trie[cur][v] = newNode(); cur = trie[cur][v]; } s[cur].push_back(str_id); } inline void build_fail(){ for(register int i = 0; i < 26; i++) if(trie[0][i]) fail[trie[0][i]] = 0, q.push(trie[0][i]); while(!q.empty()){ int u = q.front(); q.pop(); for(register int i = 0; i < 26; i++) if(trie[u][i]) fail[trie[u][i]] = trie[fail[u]][i], q.push(trie[u][i]); else trie[u][i] = trie[fail[u]][i]; } } inline void calc_times(char *str){ int len = strlen(str), cur = 0; for(register int i = 0; i < len; i++){ cur = trie[cur][str[i] - 'a']; for(register int j = cur; j; j = fail[j]) cnt[j]++; } for(register int i = 1; i <= topp; i++) if(cnt[i]){ int sz = s[i].size(); for(register int j = 0; j < sz; j++) times[s[i][j]] += cnt[i]; } } } AC; int main(){ while(scanf("%d", &N) != EOF && N){ AC.clear(); for(register int i = 1; i <= N; i++) scanf("%s", P[i]), AC.insert(P[i], i); AC.build_fail(); memset(times, 0, sizeof(times)); scanf("%s", T), AC.calc_times(T); int mxtimes = 0; for(register int i = 1; i <= N; i++) mxtimes = max(mxtimes, times[i]); printf("%d\n", mxtimes); for(register int i = 1; i <= N; i++) if(times[i] == mxtimes) puts(P[i]); } return 0; }
发表评论