#include #include #include #include #include #include using namespace std; struct Node { Node* children[36]; vector> 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& a, const pair& b) { if (a.first != b.first) return a.first > b.first; return a.second < b.second; } // 维护 top k 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(); } 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 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; }