题目描述
有 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
这题真是迷啊，开1e6的内存A了，开1e5的内存MLE
我们统计出每个节点的出现信息，然后暴力沿着$fail$树跑就行了
// luogu-judger-enable-o2 // luogu-judger-enable-o2 // luogu-judger-enable-o2 // luogu-judger-enable-o2 #include<cstdio> #include<cstring> #include<queue> #include<vector> using namespace std; const int MAXN = 1e6 + 10, B = 26; int T; char s[201][75], a[MAXN]; int N; int fail[MAXN], ch[MAXN][27], val[MAXN], root = 0, tot = 0, sum[MAXN]; void insert(char *s, int I) { int N = strlen(s + 1); int now = root; for(int i = 1; i <= N; i++) { int x = s[i] - 'a'; if(!ch[now][x]) ch[now][x] = ++tot; now = ch[now][x]; } val[now] = I; } void GetFail() { queue<int> q; for(int i = 0; i < B; i++) if(ch[root][i]) q.push(ch[root][i]); while(!q.empty()) { int p = q.front(); q.pop(); for(int i = 0; i < B; i++) if(ch[p][i]) fail[ch[p][i]] = ch[fail[p]][i], q.push(ch[p][i]); else ch[p][i] = ch[fail[p]][i]; } } int main() { #ifdef WIN32 freopen("a.in", "r", stdin); #endif while(scanf("%d", &T) && T) { memset(fail, 0, sizeof(fail)); memset(ch, 0, sizeof(ch)); memset(val, 0, sizeof(val)); memset(fail, 0, sizeof(fail)); memset(sum, 0, sizeof(sum)); memset(s, 0, sizeof(s)); for(int i = 1; i <= T; i++) scanf("%s", s[i] + 1), insert(s[i], i); GetFail(); scanf("%s", a + 1); int N = strlen(a + 1), now = root; for(int i = 1; i <= N; i++) { now = ch[now][a[i] - 'a']; for(int t = now; t; t = fail[t]) if(val[t]) sum[val[t]]++; } int ans = 0; for(int i = 1; i <= T; i++) ans = max(ans, sum[i]); printf("%d\n", ans); for(int i = 1; i <= T; i++) if(sum[i] == ans) printf("%s\n", s[i] + 1); } return 0; }