我觉得刘汝佳的做法，时间复杂度有问题。只是似乎这道题短串串长太短不好卡。比如给出的串是一坨$a$。暴力跳$last$会比较gg。
考虑如何计算一个短串在长串中的出现次数。
当短串在长串的某个位置出现的时候，这意味着它的结束位置在fail树上的祖先中某个状态是短串的终止状态。
我们会在长串经过的每个状态都去做这样一个操作来统计每个短串出现的次数。
这个可以看成在fail树上的以根为端点的链上修改操作。
由于询问可以看成是离线的，所以每次可以单点修改cnt，最后做一次前缀和。
Code
/**
* UVa Live
* Problem#4670
* Accepted
* Time: 45ms
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
typedef bool boolean; const int MaxNode = , N = , L = ; typedef class TrieNode {
public:
int cnt;
TrieNode* ch[];
TrieNode* fail;
}TrieNode; TrieNode pool[MaxNode];
TrieNode *top; TrieNode* newnode() {
top->cnt = ;
memset(top->ch, , sizeof(top->ch));
top->fail = NULL;
return top++;
} typedef class AhoCorasick {
public:
TrieNode* rt; AhoCorasick() {
top = pool;
rt = newnode();
} TrieNode* insert(char* str) {
TrieNode* p = rt;
for (int i = , c; str[i]; i++) {
c = str[i] - 'a';
if (!p->ch[c])
p->ch[c] = newnode();
p = p->ch[c];
}
return p;
} void build() {
queue<TrieNode*> que;
rt->fail = NULL;
que.push(rt);
while (!que.empty()) {
TrieNode* p = que.front();
que.pop();
for (int i = ; i < ; i++) {
TrieNode *np = p->ch[i];
if (!np) continue;
que.push(np);
TrieNode* f = p->fail;
while (f && !f->ch[i]) f = f->fail;
if (!f)
np->fail = rt;
else
np->fail = f->ch[i];
}
}
} void query(char *str) {
TrieNode *p = rt;
for (int i = ; str[i]; i++) {
int c = str[i] - 'a';
while (p && !p->ch[c]) p = p->fail;
if (!p)
p = rt;
else
p = p->ch[c];
p->cnt++;
}
for (p = top - ; p != pool; p--)
p->fail->cnt += p->cnt;
}
}AhoCorasick; int n;
AhoCorasick ac;
char S[];
char T[N][L];
TrieNode* ps[N]; inline boolean init() {
scanf("%d", &n);
if (!n) return false;
ac = AhoCorasick();
for (int i = ; i <= n; i++) {
scanf("%s", T[i]);
ps[i] = ac.insert(T[i]);
}
scanf("%s", S);
return true;
} inline void solve() {
ac.build();
ac.query(S);
int maxt = ;
for (int i = ; i <= n; i++)
if (ps[i]->cnt > maxt)
maxt = ps[i]->cnt;
printf("%d\n", maxt);
for (int i = ; i <= n; i++)
if (ps[i]->cnt == maxt)
puts(T[i]);
} int main() {
while(init())
solve();
return ;
}