128 lines
2.5 KiB
C++
128 lines
2.5 KiB
C++
#include <iostream>
|
||
#include <string>
|
||
#include <vector>
|
||
#include <algorithm>
|
||
#include <cstring>
|
||
#include <map>
|
||
|
||
using namespace std;
|
||
|
||
struct Node {
|
||
Node* children[36];
|
||
vector<pair<long long, string>> topk;
|
||
|
||
Node() {
|
||
memset(children, 0, sizeof(children));
|
||
}
|
||
};
|
||
|
||
// 字符映射：0-9 -> 0-9, a-z -> 10-35
|
||
int getIndex(char c) {
|
||
if (c >= '0' && c <= '9') return c - '0';
|
||
return c - 'a' + 10;
|
||
}
|
||
|
||
// 排序规则
|
||
bool cmp(const pair<long long,string>& a, const pair<long long,string>& b) {
|
||
if (a.first != b.first) return a.first > b.first;
|
||
return a.second < b.second;
|
||
}
|
||
|
||
// 维护 top k
|
||
void updateTopK(vector<pair<long long,string>>& v,
|
||
const pair<long long,string>& val,
|
||
int k) {
|
||
v.push_back(val);
|
||
sort(v.begin(), v.end(), cmp);
|
||
if (v.size() > k) v.pop_back();
|
||
}
|
||
|
||
class Trie {
|
||
public:
|
||
Trie(int k): k(k) {
|
||
root = new Node();
|
||
}
|
||
|
||
void insert(const string& s, long long freq) {
|
||
Node* cur = root;
|
||
|
||
for (int i = 0; i < s.size(); i++) {
|
||
int idx = getIndex(s[i]);
|
||
|
||
if (!cur->children[idx]) {
|
||
cur->children[idx] = new Node();
|
||
}
|
||
|
||
cur = cur->children[idx];
|
||
|
||
// ❗避免把完整单词加入（否则会占坑）
|
||
if (i != s.size() - 1) {
|
||
updateTopK(cur->topk, {freq, s}, k);
|
||
}
|
||
}
|
||
}
|
||
|
||
void query(const string& prefix) {
|
||
Node* cur = root;
|
||
|
||
for (char c : prefix) {
|
||
int idx = getIndex(c);
|
||
|
||
if (!cur->children[idx]) {
|
||
cout << "no suggestion\n";
|
||
return;
|
||
}
|
||
|
||
cur = cur->children[idx];
|
||
}
|
||
|
||
if (cur->topk.empty()) {
|
||
cout << "no suggestion\n";
|
||
return;
|
||
}
|
||
|
||
for (auto& [f, word] : cur->topk) {
|
||
cout << word << "\n";
|
||
}
|
||
}
|
||
|
||
private:
|
||
Node* root;
|
||
int k;
|
||
};
|
||
|
||
int main() {
|
||
ios::sync_with_stdio(false);
|
||
cin.tie(nullptr);
|
||
|
||
int n, m, k;
|
||
cin >> n >> m >> k;
|
||
|
||
map<string, long long> freqMap;
|
||
|
||
// 去重 + 保留最大频率
|
||
for (int i = 0; i < n; i++) {
|
||
long long f;
|
||
string s;
|
||
cin >> f >> s;
|
||
freqMap[s] = max(freqMap[s], f);
|
||
}
|
||
|
||
Trie trie(k);
|
||
|
||
for (auto& [s, f] : freqMap) {
|
||
trie.insert(s, f);
|
||
}
|
||
|
||
// ⭐统一控制换行（避免PE）
|
||
for (int i = 0; i < m; i++) {
|
||
string s;
|
||
cin >> s;
|
||
|
||
trie.query(s);
|
||
|
||
if (i != m - 1) cout << "\n";
|
||
}
|
||
|
||
return 0;
|
||
} |