Hướng giải của Phân Tách 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 phân tách xâu \(S\) thành chuỗi các từ trong từ điển. Ta kết hợp Quy hoạch động (DP) với cấu trúc Trie:
Gọi \(DP[i]\) là trạng thái boolean: có thể phân tách được đoạn con \(S[0 \dots i-1]\) hay không. Khởi tạo \(DP[0] = true\). Để tính \(DP[j+1]\) từ các trạng thái trước:
- Nếu \(DP[i] = true\), ta thử xem có từ nào trong từ điển bắt đầu từ chỉ số \(i\) của \(S\) không.
- Bằng cách duyệt từ chỉ số \(i\) xuôi về cuối xâu \(S\), đi trên cấu trúc Trie của từ điển:
- Tại mỗi ký tự \(S[j]\), nếu có node con trong Trie, di chuyển tiếp. Nếu gặp node đánh dấu kết thúc từ (
isEnd = true), ta có thể đặt \(DP[j + 1] = true\). - Nếu gặp đường cụt trong Trie, ta dừng lại sớm (cắt nhánh tỉa cành cực kỳ hiệu quả).
- Tại mỗi ký tự \(S[j]\), nếu có node con trong Trie, di chuyển tiếp. Nếu gặp node đánh dấu kết thúc từ (
Độ phức tạp thời gian: \(O(|S|^2)\) trong trường hợp xấu nhất, nhưng nhờ Trie cắt nhánh nên chạy cực nhanh trong thực tế.
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;
struct TrieNode {
TrieNode* children[26];
bool isEnd;
TrieNode() {
for (int i = 0; i < 26; i++) children[i] = nullptr;
isEnd = false;
}
};
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->isEnd = true;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
if (!(cin >> n)) return 0;
string s;
cin >> s;
Trie trie;
for (int i = 0; i < n; i++) {
string word;
cin >> word;
trie.insert(word);
}
int len = s.length();
vector<bool> dp(len + 1, false);
dp[0] = true;
for (int i = 0; i < len; i++) {
if (!dp[i]) continue;
TrieNode* cur = trie.root;
for (int j = i; j < len; j++) {
int idx = s[j] - 'a';
if (cur->children[idx] == nullptr) break;
cur = cur->children[idx];
if (cur->isEnd) {
dp[j + 1] = true;
}
}
}
cout << (dp[len] ? "YES" : "NO") << "\n";
return 0;
}
Nhận xét