91分 WA #1求调

标准输入:
10
qabqks
vimbirqy
cflwvxtp
klljfj
ab
nkeiid
fkypjfev
yvgp
evdhs
xaizql
qabqksatffqpjomzstjabfklljfjqevdhsqabqkscflwvxtpeevdhsmzonkeiid
0

标准输出:
3
ab

错误输出:
2
qabqks
evdhs

#include <bits/stdc++.h>
using namespace std;
const int MAXS = 26 + 5;
const int MAXN = 1000005;

int n;
string c;
int cnt;//Trie的指针
int fa[MAXN], sum[MAXN], mxn;// fa[] 表示节点 i 的父节点,  sum[] 表示以当前节点结尾的模式串在文本串中出现的次数 
char k[MAXN];//节点 i 对应的字符 
struct Tree {
	int fail, son[MAXS], end;// end 表示是否有模式串以当前节点作为结尾 
} trie[MAXN];

void build(string s) {
	int l = s.size();
	int now = 0;//当前指针
	for (int i = 0; i < l; i++) {
		if (trie[now].son[s[i] - 'a'] == 0) {
			trie[now].son[s[i] - 'a'] = ++cnt;
			fa[cnt] = now;
			k[cnt] = s[i];
		}
		now = trie[now].son[s[i] - 'a'];
	}
	trie[now].end=1;
}


void EZ_fail() {
	queue<int> q;
	for (int i = 0; i < 26; i++) { //预处理第一层 
		if (trie[0].son[i]) {
			trie[trie[0].son[i]].fail = 0;
			q.push(trie[0].son[i]);
		}
	}
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = 0; i < 26; i++) {
			if (trie[u].son[i]) {
				trie[trie[u].son[i]].fail = trie[trie[u].fail].son[i];
				q.push(trie[u].son[i]);
			} else {
				trie[u].son[i] = trie[trie[u].fail].son[i];
			}
		}
	}
}

void out(int x) {
	stack<char> q;
	while (x != 0) {
		q.push(k[x]);
		x = fa[x];
	}
	while (!q.empty()) {
		cout << q.top();
		q.pop();
	}
	printf("\n");
}

void init() {
	for (int i = 0; i <= cnt; i++) {
		for (int j = 0; j <= 26; j++) {
			trie[i].son[j] = 0;
		}
		trie[i].fail = trie[i].end = fa[i] = sum[i] = 0;
	}
	mxn = cnt = 0;
}

int query(string s) {
	int l = s.size();
	int now = 0, mx = 0;
	for (int i = 0; i < l; i++) {
		now = trie[now].son[s[i] - 'a'];
		for (int j = now; j && trie[j].end; j = trie[j].fail) {
			sum[j]++;
			if (sum[j] > mx) mx = sum[j];
		}
	}
	return mx;
}

int main() {
	cin >> n;
	while (n) {
		for (int i = 1; i <= n; i++) {
			cin >> c;
			build(c);
		}
		trie[0].fail = 0;
		cin >> c;
		
		EZ_fail();
		
		mxn = query(c);
		cout << mxn << endl;
		for (int i = 1; i <= cnt; i++) {
			if (sum[i] == mxn) out(i);
		}
		
		init();
		cin >> n;
	}
	
	return 0;
}