rockdu
题目描述
有NN个由小写字母组成的模式串以及一个文本串TT。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串TT中出现的次数最多。
输入输出格式
输入格式：
输入含多组数据。
每组数据的第一行为一个正整数NN，表示共有NN个模式串，1 \leq N \leq 1501≤N≤150。
接下去NN行，每行一个长度小于等于7070的模式串。下一行是一个长度小于等于10^6106的文本串TT。
输入结束标志为N=0N=0。
输出格式：
对于每组数据，第一行输出模式串最多出现的次数，接下去若干行每行输出一个出现次数最多的模式串，按输入顺序排列。
输入输出样例
输入样例#1： 复制
2 aba bab ababababac 6 beta alpha haha delta dede tata dedeltalphahahahototatalpha 0
输出样例#1： 复制
4 aba 2 alpha haha
模板题一道，就是输出很蛋疼。另外trie树写指针版真的快得多（1~2s），但是还是用数组比较好写。
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 1e6 + 5;
int mx = 0;
namespace Aho_Corasick {
int trie[maxn][26], fail[maxn], cnt, sum[maxn], fixed[maxn];
int init() {
cnt = 0, mx = 0;
memset(trie, 0, sizeof(trie));
memset(fail, 0, sizeof(fail));
memset(sum, 0, sizeof(sum));
memset(fixed, 0, sizeof(fixed));
fail[0] = -1;
}
int insert(char * s) {
int len = strlen(s);
int now = 0, id;
for(register int i = 0; i < len; ++i) {
id = s[i] - 'a';
if(trie[now][id]) now = trie[now][id];
else now = trie[now][id] = ++cnt;
}
++sum[now];
}
void create() {
queue<int > q;
q.push(0);
while(!q.empty()) {
int u = q.front();
q.pop();
for(register int i = 0; i < 26; ++i) {
if(!trie[u][i]) continue;
int p = fail[u];
while(~p && !trie[p][i])
p = fail[p];
if(p != -1) fail[trie[u][i]] = trie[p][i];
q.push(trie[u][i]);
}
}
}
void work(char * s) {
int len = strlen(s), now = 0;
for(register int i = 0; i < len; ++i) {
int id = s[i] - 'a';
while(now && !trie[now][id])
now = fail[now];
if(now != -1) now = trie[now][id];
int p = now;
while(p) {
++fixed[p];
if(sum[p]) mx = max(mx, fixed[p]);
p = fail[p];
}
}
}
void judge(char * s) {
int len = strlen(s), now = 0;
for(register int i = 0; i < len; ++i) {
if(!trie[now][s[i] - 'a']) return;
now = trie[now][s[i] - 'a'];
}
if(fixed[now] != mx) return ;
for(register int i = 1; i <= sum[now]; ++i)
printf("%s\n", s);
}
}
#define AC Aho_Corasick
int n, m;
char s[205][205], art[maxn];
char res[205];
int main() {
while(1) {
scanf("%d", &n);
if(n == 0) break;
AC::init();
for(register int i = 1; i <= n; ++i) {
scanf("%s", s[i]);
AC::insert(s[i]);
}
AC::create();
scanf("%s", art);
AC::work(art);
printf("%d\n", mx);
for(register int i = 1; i <= n; ++i)
AC::judge(s[i]);
}
return 0;
}
没有帐号? 立即注册