#include #include #include #include #include using namespace std; struct Node { map children; vector> topk; }; bool cmp(const pair& a, const pair& b) { if (a.first != b.first) return a.first > b.first; return a.second < b.second; } void updateTopK(vector>& v, const pair& 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 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; }