[洛谷 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;
}
发表评论