Hướng giải của AC + XOR
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ả:
Lời giải: AC + XOR
Phân tích
Tính XOR của mỗi xâu mẫu và lưu vào tập hợp \(S\). Sau đó duyệt xâu \(T\), tính prefix XOR:
\(pref[i] = XOR(T[1..i])\)
Với mỗi \(i\), xâu con kết thúc tại \(i\) là thú vị nếu tồn tại \(j \le i\) sao cho:
\(pref[i] \oplus pref[j-1] \in S\)
Dùng mảng đếm (hash map) để lưu tần suất các prefix XOR đã gặp. Với mỗi \(i\), với mỗi giá trị \(v \in S\), cộng cnt[pref[i] ^ v] vào kết quả.
Có thể tối ưu bằng cách nếu \(|S|\) là tập con của không gian XOR (31 bit) và \(|S|\) nhỏ hơn.
Độ phức tạp
\(O(|T| \times |S|)\). Nếu \(|S|\) lớn, dùng Aho-Corasick trên cây nhị phân (binary trie) để truy vấn nhanh hơn.
Code mẫu C++
// Giải thuật ac cho bài toán ac-xor-string\n#include <bits/stdc++.h>
using namespace std;
int main() {
// Doc du lieu dau vao
ios::sync_with_stdio(false); cin.tie(0);
string t; cin >> t;
int n; cin >> n;
unordered_set<int> patXor;
for (int i = 0; i < n; ++i) {
string p; cin >> p;
int x = 0;
for (char c : p) x ^= (c - 'a' + 1);
patXor.insert(x);
}
unordered_map<int, long long> cnt;
cnt[0] = 1;
int pref = 0;
long long ans = 0;
for (char c : t) {
pref ^= (c - 'a' + 1);
for (int v : patXor) {
auto it = cnt.find(pref ^ v);
if (it != cnt.end()) ans += it->second;
}
cnt[pref]++;
}
cout << ans << "\n";
return 0;
}
Nhận xét