Hướng dẫn giải của [CSES 2110] Substring Distribution
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Cách giải 1: mảng hậu tố
Ta duyệt qua mảng hậu tố và xác định, với mỗi vị trí ~i~, độ dài của các tiền tố cần được đếm.
Vì ta muốn đếm mỗi xâu con phân biệt chỉ một lần, độ dài tiền tố tối thiểu là ~\textrm{lcp}[i]+1~. Độ dài tiền tố tối đa là ~n-\textrm{sa}[i]~, là độ dài của hậu tố. Do đó, ta luôn có một đoạn độ dài liên tục.
Đầu tiên ta xây dựng một vector diff chứa các hiệu số giữa các độ dài liên tiếp. Bằng cách duyệt qua vector đó, ta có thể xác định phân bố độ dài một cách hiệu quả.
Đoạn mã sau tạo mảng hậu tố trong ~O(n \log^2 n)~ thời gian và mảng LCP trong ~O(n)~ thời gian. Sau đó, nó tính phân bố trong ~O(n)~ thời gian.
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
using ll = long long;
struct SuffixArray {
string s;
int n;
vector<int> sa;
vector<int> lcp;
SuffixArray(string x) : s(x + "$"), n(s.size()), sa(n), lcp(n) {
int bound = 1;
while (bound < n) bound *= 2;
vector<int> inv(2 * bound);
copy(s.begin(), s.end(), inv.begin());
vector<int> order(n);
iota(order.begin(), order.end(), 0);
for (int add = 1; add < bound; add *= 2) {
vector<pair<int, int>> pairs(n);
for (int i = 0; i < n; i++) {
pairs[i] = {inv[i], inv[i + add]};
}
sort(order.begin(), order.end(),
[&](int a, int b) { return pairs[a] < pairs[b]; });
int label = 1;
for (int i = 0; i < n; i++) {
label += i && pairs[order[i - 1]] != pairs[order[i]];
inv[order[i]] = label;
}
}
for (int i = 0; i < n; i++) {
inv[i]--;
sa[inv[i]] = i;
}
for (int i = 0; i < n - 1; i++) {
int k = inv[i];
if (i) lcp[k] = max(0, lcp[inv[i - 1]] - 1);
while (s[sa[k - 1] + lcp[k]] == s[sa[k] + lcp[k]]) lcp[k]++;
}
}
};
int main() {
string s;
cin >> s;
int n = s.size();
SuffixArray sa(s);
vector<int> diff(n + 2);
for (int i = 1; i <= n; i++) {
diff[sa.lcp[i] + 1]++;
diff[n - sa.sa[i] + 1]--;
}
ll count = 0;
for (int i = 1; i <= n; i++) {
count += diff[i];
cout << count << " ";
}
cout << "\n";
}
Cách giải 2: automaton hậu tố
Mỗi trạng thái của automaton hậu tố tương ứng với một tập hợp các xâu con có độ dài tạo thành một đoạn liên tục.
Trường len chứa độ dài lớn nhất của một xâu con trong trạng thái, và tất cả các xâu con khác là hậu tố của xâu con đó. Hơn nữa, trường link trỏ đến trạng thái trước đó chứa các hậu tố nhỏ hơn của xâu con.
Sử dụng các trường len và link, ta có thể xây dựng một vector diff tương tự như trong cách giải trước, và sau đó xây dựng phân bố độ dài.
Việc xây dựng automaton hậu tố mất ~O(n)~ thời gian, và tính phân bố cũng mất ~O(n)~ thời gian.
#include <iostream>
#include <map>
#include <vector>
using namespace std;
using ll = long long;
struct SuffixAutomaton {
struct State {
int len;
State *link;
map<char, State *> next;
bool seen;
};
vector<int> diff;
State *first, *last;
SuffixAutomaton(string s) : diff(s.size() + 2) {
first = last = new State{};
for (auto c : s) {
auto *add = new State{};
add->len = last->len + 1;
add->link = first;
State *cur = last;
while (cur && !cur->next[c]) {
cur->next[c] = add;
cur = cur->link;
}
if (cur && cur->next[c] != add) {
State *mid = cur->next[c];
if (cur->len + 1 == mid->len) {
add->link = mid;
} else {
auto *copy = new State(*mid);
copy->len = cur->len + 1;
add->link = mid->link = copy;
while (cur && cur->next[c] == mid) {
cur->next[c] = copy;
cur = cur->link;
}
}
}
last = add;
}
dfs(first);
}
void dfs(State *cur) {
if (cur->seen) return;
cur->seen = true;
if (cur != first) {
diff[cur->len + 1]--;
diff[cur->link->len + 1]++;
}
for (auto [c, p] : cur->next) {
dfs(p);
}
}
};
int main() {
string s;
cin >> s;
int n = s.size();
SuffixAutomaton sa(s);
ll count = 0;
for (int i = 1; i <= n; i++) {
count += sa.diff[i];
cout << count << " ";
}
cout << "\n";
}
Tài liệu tham khảo
Chương trình tham khảo
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
using ll = long long;
struct SuffixArray {
string s;
int n;
vector<int> sa;
vector<int> lcp;
SuffixArray(string x) : s(x + "$"), n(s.size()), sa(n), lcp(n) {
int bound = 1;
while (bound < n) bound *= 2;
vector<int> inv(2 * bound);
copy(s.begin(), s.end(), inv.begin());
vector<int> order(n);
iota(order.begin(), order.end(), 0);
for (int add = 1; add < bound; add *= 2) {
vector<pair<int, int>> pairs(n);
for (int i = 0; i < n; i++) {
pairs[i] = {inv[i], inv[i + add]};
}
sort(order.begin(), order.end(),
[&](int a, int b) { return pairs[a] < pairs[b]; });
int label = 1;
for (int i = 0; i < n; i++) {
label += i && pairs[order[i - 1]] != pairs[order[i]];
inv[order[i]] = label;
}
}
for (int i = 0; i < n; i++) {
inv[i]--;
sa[inv[i]] = i;
}
for (int i = 0; i < n - 1; i++) {
int k = inv[i];
if (i) lcp[k] = max(0, lcp[inv[i - 1]] - 1);
while (s[sa[k - 1] + lcp[k]] == s[sa[k] + lcp[k]]) lcp[k]++;
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
int n = s.size();
SuffixArray sa(s);
vector<int> diff(n + 2);
for (int i = 1; i <= n; i++) {
diff[sa.lcp[i] + 1]++;
diff[n - sa.sa[i] + 1]--;
}
ll count = 0;
for (int i = 1; i <= n; i++) {
count += diff[i];
cout << count << " ";
}
cout << "\n";
}
Bình luận