Hướng giải của Xóa ít nhấ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ả:
Phân tích
Xây dựng automaton Aho-Corasick. Đánh dấu các trạng thái chứa từ cấm. Dùng DP: \(dp[i][u]\) = số ký tự tối thiểu cần xóa ở tiền tố \(i\) để kết thúc ở trạng thái \(u\). Tại bước \(i\) có hai lựa chọn: giữ ký tự (chuyển trạng thái) hoặc xóa (giữ nguyên trạng thái, tăng số lần xóa). Độ phức tạp \(O(\|T\| \times |AC|)\).
Code mẫu C++
// Giải thuật ac cho bài toán ac-bad-words\n#include <bits/stdc++.h>
using namespace std;
const int ALPHABET = 26;
const int INF = 1e9;
struct AhoCorasick {
struct Node {
int next[ALPHABET];
int fail;
bool bad;
Node() {
fill(next, next + ALPHABET, -1);
fail = 0; bad = false;
}
};
vector<Node> trie;
AhoCorasick() { trie.emplace_back(); }
void insert(const string& s) {
int node = 0;
for (char ch : s) {
int c = ch - 'a';
if (trie[node].next[c] == -1) {
trie[node].next[c] = trie.size();
trie.emplace_back();
}
node = trie[node].next[c];
}
trie[node].bad = true;
}
void build() {
queue<int> q;
for (int c = 0; c < ALPHABET; c++) {
if (trie[0].next[c] != -1) {
trie[trie[0].next[c]].fail = 0;
q.push(trie[0].next[c]);
} else {
trie[0].next[c] = 0;
}
}
while (!q.empty()) {
int u = q.front(); q.pop();
if (trie[trie[u].fail].bad)
trie[u].bad = true;
for (int c = 0; c < ALPHABET; c++) {
if (trie[u].next[c] != -1) {
trie[trie[u].next[c]].fail = trie[trie[u].fail].next[c];
q.push(trie[u].next[c]);
} else {
trie[u].next[c] = trie[trie[u].fail].next[c];
}
}
}
}
};
int main() {
// Doc du lieu dau vao
ios::sync_with_stdio(false); cin.tie(0);
string t; cin >> t;
int k; cin >> k;
AhoCorasick aho;
for (int i = 0; i < k; i++) {
string s; cin >> s;
aho.insert(s);
}
aho.build();
int S = aho.trie.size();
int n = t.size();
vector<int> dp(S, INF);
dp[0] = 0;
for (int i = 0; i < n; i++) {
// Duyet qua tung phan tu
vector<int> ndp(S, INF);
int c = t[i] - 'a';
for (int u = 0; u < S; u++) {
if (dp[u] == INF) continue;
ndp[u] = min(ndp[u], dp[u] + 1);
int v = aho.trie[u].next[c];
if (!aho.trie[v].bad)
ndp[v] = min(ndp[v], dp[u]);
}
dp = move(ndp);
}
int ans = INF;
for (int u = 0; u < S; u++)
ans = min(ans, dp[u]);
cout << ans << "\n";
return 0;
}
Nhận xét