Hướng dẫn giải của TMP2526_CAU3
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
Bài yêu cầu tìm độ dài xâu con dài nhất xuất hiện ít nhất hai lần trong S. Nhận xét: nếu một xâu con dài L xuất hiện hai lần, thì hai hậu tố bắt đầu tại hai vị trí đó có chung tiền tố dài ít nhất L. Ngược lại, nếu hai hậu tố có chung tiền tố dài L thì xâu con đó xuất hiện hai lần. Vậy đáp án là độ dài chung lớn nhất (LCP) của hai hậu tố khác nhau của S.
Sub 1: Vét cạn — ~O(N^3)~, dùng khi ~N \le 3~
Thử mọi cặp vị trí (i, j) với i < j, rồi so sánh từng ký tự để đếm độ dài chung. Với ~N \le 3~ chỉ có vài cặp nên chạy rất nhanh. Nếu chỉ nộp sub này: đúng 18/23 test.
Sub 2: Quy hoạch động trên cặp vị trí — ~O(N^2)~, dùng khi ~N \le 200~
Gọi lcp[i][j] là độ dài chung của hậu tố bắt đầu tại i và tại j. Nếu S[i] = S[j] thì ~lcp[i][j] = lcp[i+1][j+1] + 1~, ngược lại bằng 0. Đáp án là max lcp[i][j] với i < j. Tính từ cuối xâu về đầu để lcp[i+1][j+1] đã có sẵn. Nếu chỉ nộp sub này: đúng 17/23 test (6 test còn lại quá giờ vì N lớn hơn miền của sub).
Sub 3: Mảng hậu tố + mảng LCP — ~O(N \log^2 N)~, dùng cho mọi ~N~
Sắp xếp các hậu tố theo thứ tự từ điển bằng cách nhân đôi độ dài (prefix doubling): mỗi vòng so sánh cặp hạng (rk[i], rk[i + k]) rồi dừng khi mọi hạng khác nhau. Sau đó dùng thuật toán Kasai tính LCP của hai hậu tố liền kề trong thứ tự sắp xếp. Đáp án là LCP lớn nhất trong mảng đó, vì hai hậu tố có LCP lớn nhất luôn đứng cạnh nhau sau khi sắp xếp. Lưu ý: bài này đếm cả các lần xuất hiện chồng lấn nhau (VD "aaa" có "aa" hai lần). Ví dụ 4 của đề xác nhận điều này: "chuc" xuất hiện ở vị trí 1 và 4 của "chuchucik..." (chồng lấn một ký tự) và đáp án là 4. Nếu chỉ nộp sub này: đúng 23/23 test.
Chương trình hoàn chỉnh
Hàm main đọc xâu S. Nếu ~N \le 3~ gọi sub1, nếu ~N \le 200~ gọi sub2, các trường hợp còn lại gọi sub3.
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
// Sub 1: vet can, thu moi cap vi tri (i, j), i < j, so sanh tung ky tu. O(n^3). Dung khi n <= 3
void sub1() {
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
int len = 0;
while (j + len < n && s[i + len] == s[j + len]) len++; // do dai chung cua 2 hau to
ans = max(ans, len);
}
cout << ans << "\n";
}
// Sub 2: quy hoach dong. lcp[i][j] = do dai chung dai nhat cua hau to bat dau tu i va j.
// lcp[i][j] = lcp[i+1][j+1] + 1 neu s[i] == s[j]. Dap an la max lcp[i][j] voi i < j. O(n^2). Dung khi n <= 200
void sub2() {
vector<vector<int>> lcp(n + 1, vector<int>(n + 1, 0));
int ans = 0;
for (int i = n - 1; i >= 0; i--)
for (int j = n - 1; j > i; j--) {
if (s[i] == s[j]) lcp[i][j] = lcp[i + 1][j + 1] + 1;
ans = max(ans, lcp[i][j]);
}
cout << ans << "\n";
}
// Sub 3: mang hau to (suffix array) + mang LCP (Kasai). Dap an la LCP lon nhat giua 2 hau to lien tiep
// trong thu tu tu dien. O(n log^2 n). Dung cho moi n
void sub3() {
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;
}
// Kasai: lcp[i] = do dai chung cua sa[i-1] va sa[i]
vector<int> lcp(n, 0), pos(n);
for (int i = 0; i < n; i++) pos[sa[i]] = i;
int h = 0, ans = 0;
for (int i = 0; i < n; i++) {
if (pos[i] > 0) {
int j = sa[pos[i] - 1];
while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
lcp[pos[i]] = h;
ans = max(ans, h);
if (h > 0) h--;
} else {
h = 0;
}
}
cout << ans << "\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 <= 3) sub1();
else if (n <= 200) sub2();
else sub3();
return 0;
}
Bình luận