Hướng dẫn giải của Bài 4 (đề An Giang 2021)
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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 chuỗi lặp lại (bình phương) dài nhất là xâu con của S; S có thể chứa dấu cách.
Sub 1: Vét cạn, ~O(n^3)~
Với nửa độ dài h giảm dần, thử mọi vị trí i; lấy vị trí đầu tiên thỏa mãn. Đúng 10/10 test.
Sub 2: LCP, ~O(n^2)~
lcp[i][j] là độ dài chung dài nhất của hai hậu tố; S[i..i+2h-1] là chuỗi lặp khi lcp[i][i+h] ≥ h. Đúng 10/10 test.
Chương trình hoàn chỉnh
main đọc cả dòng S (getline) và gọi sub1 (|S| ≤ 60), còn lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
string S;
// Sub 1: vet can. Voi nua do dai h (tu lon den nho), thu moi vi tri i:
// neu S[i..i+h-1] == S[i+h..i+2h-1] thi day la chuoi lap lai dai nhat can tim (lay vi tri dau tien).
void sub1() {
int n = S.size();
for (int h = n / 2; h >= 1; h--)
for (int i = 0; i + 2 * h <= n; i++) {
bool ok = true;
for (int k = 0; k < h && ok; k++) ok = S[i + k] == S[i + h + k];
if (ok) {
cout << S.substr(i, 2 * h) << "\n";
return;
}
}
cout << "KHONG TIM DUOC\n";
}
// Sub 2: lcp[i][j] = do dai chung dai nhat cua hai hau to bat dau tai i va j (tinh tu cuoi xau).
// Doan S[i..i+2h-1] la chuoi lap lai khi lcp[i][i+h] >= h. Duyet h giam dan, i tang dan.
void sub2() {
int n = S.size();
vector<vector<int>> lcp(n + 2, vector<int>(n + 2, 0));
for (int i = n - 1; i >= 0; i--)
for (int j = n - 1; j >= 0; j--)
if (S[i] == S[j]) lcp[i][j] = lcp[i + 1][j + 1] + 1;
for (int h = n / 2; h >= 1; h--)
for (int i = 0; i + 2 * h <= n; i++)
if (lcp[i][i + h] >= h) {
cout << S.substr(i, 2 * h) << "\n";
return;
}
cout << "KHONG TIM DUOC\n";
}
int main() {
freopen("bai04.inp", "r", stdin);
freopen("bai04.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
getline(cin, S); // xau co the chua dau cach
if (!S.empty() && S.back() == '\r') S.pop_back();
if (S.size() <= 60) sub1();
else sub2();
return 0;
}
Bình luận