Hướng dẫn giải của Xâu con dài nhất (đề HSG 12 Phú Thọ 2025-2026)
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.
Hướng dẫn giải
Tìm độ dài lớn nhất của một xâu con xuất hiện ít nhất hai lần trong $S$ (hai lần xuất hiện được phép chồng lên nhau). Đây là bài tìm độ dài lặp dài nhất của xâu: đáp số bằng LCP lớn nhất giữa hai hậu tố khác nhau của $S$.
Sub 1: Vét cạn từng cặp vị trí — ~O(n^3)~, dùng khi ~n \le 200~
Với mỗi cặp vị trí $i < j$, so sánh từng ký tự từ $si$ và $sj$ đến khi khác nhau, lấy độ dài chung lớn nhất.
Nếu chỉ nộp sub này: đúng 17/23 test (6 test lớn quá giờ).
Sub 2: Mảng hậu tố và LCP — ~O(n \log^2 n)~
Sắp xếp các hậu tố bằng cách nhân đôi độ dài (mỗi vòng so sánh cặp hạng của $i$ và $i + k$). Sau đó dùng thuật toán Kasai tính LCP giữa hai hậu tố liền kề trong thứ tự đã sắp, và lấy giá trị lớn nhất. Bẫy: hai hậu tố có thể chồng lên nhau, ví dụ aaa có đáp số $2$ từ hai hậu tố aa và aaa.
Nếu chỉ nộp sub này: đúng 23/23 test.
Chương trình hoàn chỉnh
main đọc dữ liệu từ file CAU3.INP, ghi ra CAU3.OUT. Nếu $n \le 200$ thì gọi sub 1, còn lại gọi sub 2.
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
// Sub 1: vet can O(n^3), dung khi n <= 200.
// Thu moi cap vi tri i < j, do do dai chung dai nhat cua hai xau con bat dau tu i va tu j.
void sub1() {
int best = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
int k = 0;
while (j + k < n && s[i + k] == s[j + k]) k++;
best = max(best, k);
}
cout << best << "\n";
}
// Sub 2: mang hau sa (suffix array) + LCP, dung cho moi n.
// Dap an = LCP lon nhat giua hai hau to bat ky = LCP lon nhat giua hai hau to ke nhau sau khi sap xep.
void sub2() {
vector<int> sa(n), rk(n), tmp(n);
for (int i = 0; i < n; i++) {
sa[i] = i;
rk[i] = s[i];
}
for (int k = 1;; k <<= 1) {
auto cmp = [&](int x, int y) {
if (rk[x] != rk[y]) return rk[x] < rk[y];
int rx = x + k < n ? rk[x + k] : -1;
int ry = y + k < n ? rk[y + k] : -1;
return rx < ry;
};
sort(sa.begin(), sa.end(), cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++) tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
rk = tmp;
if (rk[sa[n - 1]] == n - 1) break; // cac hau to da phan biet
}
// Kasai: lcp[i] = LCP(hau to sa[i-1], hau to sa[i])
vector<int> lcp(n, 0);
int h = 0, best = 0;
for (int i = 0; i < n; i++) {
if (rk[i] > 0) {
int j = sa[rk[i] - 1];
while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
lcp[rk[i]] = h;
best = max(best, h);
if (h > 0) h--;
} else {
h = 0;
}
}
cout << best << "\n";
}
int main() {
freopen("CAU3.INP", "r", stdin);
freopen("CAU3.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> s;
n = s.size();
if (n <= 200) sub1();
else sub2();
return 0;
}
Bình luận