10分求调(字典树)
查看原帖
10分求调(字典树)
1120049
LiYAOo楼主2024/9/1 11:09
#include <bits/stdc++.h>
using namespace std;
const int N = 10000 * 50 + 5;

int trie[N][26];
int word[N], cnt[N]; //用于记录以这个结点为单词末尾单词个数和点名次数
char s[60];
int n, m, idx = 0;

void insert(char *s) {
	int u = 0;
	for (int i = 0; s[i]; i++) {
		int j = s[i] - 'a';
		if (trie[u][j] == 0) {
			trie[u][j] = ++idx;
		}
		u = trie[u][j];
	}
	word[u]++;
}

int find(char *s) {
	int u = 0;
	for (int i = 0; s[i]; i++) {
		int j = s[i] - 'a';
		if (trie[u][j] == 0) {
			return -1;//没有这个单词
		}
		u = trie[u][j];
	}
	if (word[u]) {
		return cnt[u]++;//存在的话则增加次数
	} else {
		return -1;
	}
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s;
		insert(s);
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> s;
		if (find(s) == -1) cout << "WRONG" << '\n';
		else if (find(s) == 0) cout << "OK" << '\n';
		else cout << "REPEAT" << '\n';
	}
	return 0;
}
2024/9/1 11:09
加载中...