Hướng giải của Đếm Tần Suất Tiền Tố
Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Tác giả:
Hướng dẫn giải
Bài toán đếm số lượng từ bắt đầu bằng một tiền tố \(P\).
Để giải bài toán này hiệu quả, ta lưu thêm một biến số nguyên count ở mỗi node của Trie.
- Khi Insert: Khi đi qua mỗi ký tự của từ, ta cộng giá trị
countcủa node tương ứng thêm \(1\). - Khi truy vấn tiền tố \(P\): Ta duyệt theo các ký tự của \(P\) đến node cuối cùng. Giá trị
counttại node cuối này chính là số lượng từ có tiền tố \(P\). Nếu không đi tiếp được hết tiền tố \(P\), kết quả là \(0\).
Độ phức tạp thời gian:
- Thêm từ: \(O(|S|)\)
- Truy vấn: \(O(|P|)\)
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;
struct TrieNode {
TrieNode* children[26];
int count;
TrieNode() {
for (int i = 0; i < 26; i++) {
children[i] = nullptr;
}
count = 0;
}
};
struct Trie {
TrieNode* root;
Trie() { root = new TrieNode(); }
void insert(const string& s) {
TrieNode* cur = root;
for (char c : s) {
int idx = c - 'a';
if (cur->children[idx] == nullptr) {
cur->children[idx] = new TrieNode();
}
cur = cur->children[idx];
cur->count++; // Cộng dồn số từ đi qua node này
}
}
int countPrefix(const string& s) {
TrieNode* cur = root;
for (char c : s) {
int idx = c - 'a';
if (cur->children[idx] == nullptr) return 0;
cur = cur->children[idx];
}
return cur->count;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int q;
if (!(cin >> q)) return 0;
Trie trie;
while (q--) {
int t;
string s;
cin >> t >> s;
if (t == 1) {
trie.insert(s);
} else {
cout << trie.countPrefix(s) << "\n";
}
}
return 0;
}
Nhận xét