给出N个模式串,然后我们用一个文本串去进行匹配,这样的做法,就是AC自动机了,于是乎,我们可以先将N个模式串丢进去,然后建立fail树,然后先对所有的节点求出最大串在文本串中出现的次数,然后利用dfs跑fail树的办法,我们可以O(N)的求解这个问题。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define pii pair<int, int>
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 70 * 150 + 7;
int N, tot, root;
struct Trie_node
{
int nex[26], val, fail;
Trie_node() { memset(nex, 0, sizeof(nex)); val = 0; fail = 0; }
void clear() { memset(nex, 0, sizeof(nex)); val = 0; fail = 0; }
} t[maxN];
char s[155][77], T[1000006];
void Insert(int ith)
{
int len = (int)strlen(s[ith]), u = root;
for(int i=0, id; i<len; i++)
{
id = s[ith][i] - 'a';
if(!t[u].nex[id])
{
t[u].nex[id] = ++tot;
t[tot].clear();
}
u = t[u].nex[id];
}
t[u].val = ith;
}
int que[maxN], top, tail;
void build_fail()
{
top = tail = 0;
que[tail++] = root;
int tmp, p, son;
while(top < tail)
{
tmp = que[top++];
for(int i=0; i<26; i++)
{
son = t[tmp].nex[i];
if(son)
{
if(!tmp) t[son].fail = 0;
else
{
p = t[tmp].fail;
while(p && !t[p].nex[i]) p = t[p].fail;
t[son].fail = t[p].nex[i];
}
if(t[t[son].fail].val) t[son].val += t[t[son].fail].val;
que[tail++] = son;
}
else t[tmp].nex[i] = t[t[tmp].fail].nex[i];
}
}
}
vector<int> to[maxN];
int siz[maxN] = {0}, maxx;
vector<int> ans;
void dfs(int u)
{
for(int v : to[u])
{
dfs(v);
siz[u] += siz[v];
}
if(t[u].val)
{
if(siz[u] > maxx)
{
maxx = siz[u];
ans.clear();
ans.push_back(t[u].val);
}
else if(siz[u] == maxx) ans.push_back(t[u].val);
}
}
int main()
{
while(scanf("%d", &N) && N)
{
tot = 0; root = 0;
t[root].clear();
for(int i=1; i<=N; i++)
{
scanf("%s", s[i]);
Insert(i);
}
build_fail();
for(int i=0; i<=tot; i++) { to[i].clear(); siz[i] = 0; }
for(int i=1; i<=tot; i++) to[t[i].fail].push_back(i);
scanf("%s", T);
int u = root, len = (int)strlen(T);
for(int i=0, id; i<len; i++)
{
id = T[i] - 'a';
while(u && !t[u].nex[id]) u = t[u].fail;
u = t[u].nex[id];
siz[u]++;
}
maxx = 0; ans.clear();
dfs(root);
printf("%d\n", maxx);
sort(ans.begin(), ans.end());
for(int i : ans)
{
printf("%s\n", s[i]);
}
}
return 0;
}