[洛谷 3796]【模板】AC自动机(加强版)

  • 2018-02-27
  • 0
  • 0

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;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai