求助,实在找不出错误在哪
查看原帖
求助,实在找不出错误在哪
597716
IT__windy楼主2022/5/8 02:45
#include<bits/stdc++.h>
#define N 1000005
using namespace std;
string str[N];
int trie[N][26], ed[N], kmp[N];
int tot, n;
struct result {
	int pos;
	int num;
	bool operator <(const result &a)const {
		if (num != a.num)return pos < a.pos;
		return num > a.num;
	}
} ans[N];
void insert(string s, int num) {
	int len = s.length(), p = 0, ch;
	for (int i = 0; i < len; i++) {
		ch = s[i] - 'a';
		if (!trie[p][ch])trie[p][ch] = ++tot;
		p = trie[p][ch];
	}
	ed[p] = num;
}
void get_kmp() {
	queue<int>q;
	int x, y;
	for (int i = 0; i < 26; i++)
		if (trie[0][i])
			q.push(trie[0][i]);
	while (!q.empty()) {
		x = q.front();
		q.pop();
		for (int i = 0; i < 26; i++) {
			y = trie[x][i];
			if (y) {
				kmp[y] = trie[kmp[x]][i];
				q.push(y);
			} else
				trie[x][i] = trie[kmp[x]][i];
		}
	}
}
void init() {
	memset(trie, 0, sizeof(trie));
	memset(ed, 0, sizeof(ed));
	memset(kmp, 0, sizeof(kmp));
	tot = 0;
}
void query(string s) {
	int len = s.length();
	int p = 0;
	for (int i = 0; i < len; i++) {
		p = trie[p][s[i] - 'a'];
		for (int k = p; k; k = kmp[k])
			ans[ed[k]].num++;
	}
	sort(&ans[1], &ans[n + 1]);
	printf("%d\n", ans[1].num);
	for (int i = 1; i <= n; i++) {
		cout << str[ans[i].pos] << endl;;
		if (ans[i].num != ans[i + 1].num)
			break;
	}
	return;
}
int main() {
	while (1) {
		scanf("%d", &n);
		if (!n)return 0;
		init();
		for (int i = 1; i <= n; i++) {
			cin >> str[i];
			ans[i].pos = i;
			ans[i].num = 0;
			insert(str[i], i);
		}
		get_kmp();
		cin >> str[0];
		query(str[0]);
	}
	return 0;
}
2022/5/8 02:45
加载中...