JZTXT

字符串

发布时间 2023-10-31 20:05:06作者: hnzzlxs01

字典树

板子题1号， 求某字符串是否出现过及出现几次

AC Code:

#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e5 + 5;

int n, m;

string s;

int trie[maxn][26], tot;
int fend[maxn];

void insert(string s) {// 加入
	int len = s.size(), p = 1;
	for (int i = 0; i < len; i++) {
		int ch = s[i] - 'a';
		if (!trie[p][ch]) {
			trie[p][ch] = ++tot;
		}
		p = trie[p][ch];
	}
	fend[p] = 1;
}

int search(string s) {// 查是否存在及查询次数
	int len = s.size(), p = 1;
	for (int i = 0; i < len; i++) {
		int ch = s[i] - 'a';
		p = trie[p][ch];
		if (!p) return 0;
	}
	return fend[p]++;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> s;
		insert(s);
	}

	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> s;
		int sum = search(s);
		if (sum) {
			if (sum == 1) {
				cout << "OK" << "\n";
			} else cout << "REPEAT" << "\n";
		} else cout << "WRONG" << "\n";
	}
	return 0;
}