Hướng dẫn giải của xâu đối xứng dài nhất_
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu tìm độ dài của xâu đối xứng (palindrome) dài nhất trong một xâu đã cho. Xâu đối xứng là xâu đọc từ trái sang phải giống hệt như từ phải sang trái. Xâu đối xứng con có thể là xâu lẻ (có ký tự ở giữa) hoặc xâu chẵn (không có ký tự ở giữa, hoặc có 2 ký tự ở giữa giống nhau).
Các cách tiếp cận
Cách Manacher (Transformed String)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
freopen("xaudx.inp", "r", stdin);
freopen("xaudx.out", "w", stdout);
string s;
cin >> s;
int n = s.size();
// Tạo chuỗi t với các ký tự phân cách (#)
// Ví dụ: aba -> ^#a#b#a#$
string t;
t.reserve(2 * n + 3);
t.push_back('^');
t.push_back('#');
for (char c : s) {
t.push_back(c);
t.push_back('#');
}
t.push_back('$');
int m = t.size();
vector<int> p(m, 0);
int center = 0, right = 0;
int maxLen = 0;
for (int i = 1; i < m - 1; i++) {
int mirror = 2 * center - i;
if (i < right)
p[i] = min(right - i, p[mirror]);
// Mở rộng palindrome
while (t[i + (1 + p[i])] == t[i - (1 + p[i])])
p[i]++;
// Cập nhật center, right
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
// Cập nhật kết quả (bỏ qua ký tự phân cách)
if (p[i] > maxLen)
maxLen = p[i];
}
cout << maxLen << endl;
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(n)
Thuật toán Manacher hoạt động bằng cách biến đổi xâu đầu vào thành một xâu có độ dài lẻ (thêm ký tự '#' vào giữa các ký tự) để xử lý统一 trường hợp xâu chẵn và lẻ. Sau đó, nó sử dụng một mảng p để lưu độ dài bán kính của palindrome đối xứng tại mỗi vị trí. Nhờ tận dụng tính đối xứng qua trung tâm center và biên phải right, ta có thể tính toán giá trị p[i] cho các vị trí một cách nhanh chóng mà không cần duyệt lại từ đầu. Điều này giúp thuật toán có độ phức tạp tuyến tính O(n).
Cách Manacher (Tách biệt Lẻ & Chẵn)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
freopen("xaudx.inp", "r", stdin);
freopen("xaudx.out", "w", stdout);
string s;
cin >> s;
int n = s.size();
// Xử lý palindrome có độ dài lẻ
vector<int> d1(n);
int l = 0, r = -1;
for (int i = 0; i < n; i++) {
int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
while (i - k >= 0 && i + k < n && s[i - k] == s[i + k])
k++;
d1[i] = k;
if (i + k - 1 > r) {
l = i - k + 1;
r = i + k - 1;
}
}
// Xử lý palindrome có độ dài chẵn
vector<int> d2(n);
l = 0, r = -1;
for (int i = 0; i < n; i++) {
int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] == s[i + k])
k++;
d2[i] = k;
if (i + k - 1 > r) {
l = i - k;
r = i + k - 1;
}
}
int maxLen = 0;
for (int len : d1) maxLen = max(maxLen, 2 * len - 1);
for (int len : d2) maxLen = max(maxLen, 2 * len);
cout << maxLen << endl;
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(n)
Đây là một biến thể khác của Manacher, không dùng xâu trung gian với ký tự '#'. Thay vào đó, nó chạy 2 vòng lặp riêng biệt: một cho palindrome lẻ và một cho palindrome chẵn. Mảng d1[i] lưu bán kính (nửa độ dài) của palindrome lẻ tâm tại i, còn d2[i] lưu bán kính của palindrome chẵn tâm tại i (khoảng giữa i-1 và i). Phương pháp này cũng có độ phức tạp tuyến tính nhưng có thể ngắn gọn và trực quan hơn trong một số trường hợp.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n) | O(n) | Manacher (Transformed String) |
| 2 | O(n) | O(n) | Manacher (Tách biệt Lẻ & Chẵn) |
Bài học kinh nghiệm
- Việc thêm các ký tự phân cách (như '#') vào xâu ban đầu giúp xử lý统一 cả xâu đối xứng chẵn và lẻ chỉ với một thuật toán duy nhất.
- Thuật toán Manacher充分利用 tính đối xứng của các xâu con đối xứng để tránh lặp lại các phép tính, giảm độ phức tạp từ O(n^2) xuống O(n).
Lỗi thường gặp
- Quên kiểm tra biên khi duyệt mở rộng xâu đối xứng (vượt quá độ dài xâu hoặc âm chỉ số), dẫn đến lỗi runtime.
- Sai lệch trong việc tính toán chỉ số Mirror hoặc cập nhật biên phải (right boundary), dẫn đến kết quả không chính xác.
Bình luận