模板
(Problem:) 找出哪些模式串在文本串 (T) 中出现的次数最多。
(templete:)(Luogu P3796)
(Code)
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e6 + 5 , M = 155 * 75;
int n , tot;
int tr[M][26] , fail[M * 26] , tag[M * 26] , id[M * 26] , sum[155] , q[M * 26];
char s[N] , str[155][75];
void insert(int x)
{
int len = strlen(str[x]) , u = 0;
for(register int i = 0; i < len; i++)
{
int ch = str[x][i] - 'a';
if (!tr[u][ch]) tr[u][ch] = ++tot;
u = tr[u][ch];
}
tag[u] = 1 , id[u] = x;
}
void get_fail()
{
int h = 0 , t = 0;
for(register int i = 0; i < 26; i++) if (tr[0][i]) q[++t] = tr[0][i];
while (h < t)
{
int now = q[++h];
for(register int i = 0; i < 26; i++)
{
if (tr[now][i]) fail[tr[now][i]] = tr[fail[now]][i] , q[++t] = tr[now][i];
else tr[now][i] = tr[fail[now]][i];
}
}
}
void query()
{
int len = strlen(s) , u = 0;
for(register int i = 0; i < len; i++)
{
int ch = s[i] - 'a';
u = tr[u][ch];
int v = u;
while (v)
{
if (tag[v] != 0) ++sum[id[v]];
v = fail[v];
}
}
int Mx = 0;
for(register int i = 1; i <= n; i++) Mx = max(Mx , sum[i]);
printf("%d
" , Mx);
for(register int i = 1; i <= n; i++)
if (sum[i] == Mx) printf("%s
" , str[i]);
}
int main()
{
scanf("%d" , &n);
while (n != 0)
{
tot = 0;
memset(tr , 0 , sizeof tr) , memset(fail , 0 , sizeof fail);
memset(tag , 0 , sizeof tag) , memset(q , 0 , sizeof q);
memset(id , 0 , sizeof id) , memset(sum , 0 , sizeof sum);
for(register int i = 1; i <= n; i++) scanf("%s" , str[i]) , insert(i);
get_fail();
scanf("%s" , s);
query();
scanf("%d" , &n);
}
}