106 lines
2.0 KiB
C++
106 lines
2.0 KiB
C++
#include <iostream>
|
|
#include <string>
|
|
#include <map>
|
|
#include <vector>
|
|
#include <algorithm>
|
|
|
|
using namespace std;
|
|
|
|
struct Node {
|
|
map<char, Node*> children;
|
|
vector<pair<long long, string>> topk;
|
|
};
|
|
|
|
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;
|
|
}
|
|
|
|
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();
|
|
}
|
|
|
|
//显然是Tier树 + 节点维护topk
|
|
class Tier {
|
|
public:
|
|
Tier(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++) {
|
|
char c = s[i];
|
|
|
|
if (!cur->children.count(c)) {
|
|
cur->children[c] = new Node();
|
|
}
|
|
|
|
cur = cur->children[c];
|
|
|
|
if (i != s.size() - 1) {
|
|
updateTopK(cur->topk, {freq, s}, k);
|
|
}
|
|
}
|
|
}
|
|
|
|
void query(const string& prefix) {
|
|
Node* cur = root;
|
|
|
|
for (char c : prefix) {
|
|
if (!cur->children.count(c)) {
|
|
cout << "no suggestion\n";
|
|
return;
|
|
}
|
|
cur = cur->children[c];
|
|
}
|
|
|
|
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() {
|
|
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);
|
|
}
|
|
|
|
Tier trie(k);
|
|
|
|
for (auto& [s, f] : freqMap) {
|
|
trie.insert(s, f);
|
|
}
|
|
bool last = false;
|
|
for (int i = 0; i < m; i++) {
|
|
string s;
|
|
cin >> s;
|
|
|
|
trie.query(s);
|
|
|
|
if (i != m - 1) cout << "\n";
|
|
}
|
|
return 0;
|
|
} |