Thuật toán Manacher tìm chuỗi con palindrome dài nhất (và bán kính palindrome tại mọi tâm) trong .
Ý tưởng
Định nghĩa = bán kính palindrome lớn nhất có tâm tại (tức là là palindrome, ).
Thay vì tính từ đầu mỗi tâm, Manacher tận dụng tính đối xứng: nếu đang biết palindrome có tâm , thì với , bán kính ít nhất bằng — phần còn nằm trong .
Xử lý palindrome chẵn/lẻ
Chèn ký tự # giữa các ký tự (và đầu/cuối) để gộp hai trường hợp:
s = a b a a b
s' = # a # b # a # a # b #
index 0 1 2 3 4 5 6 7 8 9 10
p 0 1 0 3 0 1 4 1 0 1 0
p[i] trên xâu biến đổi tương ứng với bán kính palindrome trong xâu gốc. Palindrome dài nhất trong xâu gốc có độ dài .
Cài đặt
// Trả về mảng p[] trên xâu đã biến đổi
vector<int> manacher(const string& s) {
// Biến đổi s → t
string t = "#";
for (char c : s) { t += c; t += '#'; }
int n = t.size();
vector<int> p(n, 0);
int c = 0, r = 0; // palindrome [c-r, c+r] hiện tại
for (int i = 0; i < n; i++) {
if (i < r)
p[i] = min(r - i, p[2*c - i]);
// Mở rộng
while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n
&& t[i - p[i] - 1] == t[i + p[i] + 1])
p[i]++;
// Cập nhật cửa sổ
if (i + p[i] > r) {
c = i;
r = i + p[i];
}
}
return p; // kích thước palindrome gốc = p[i]
}
Ứng dụng thường gặp
1. Độ dài palindrome dài nhất:
string s; cin >> s;
auto p = manacher(s);
int ans = *max_element(p.begin(), p.end());
cout << ans << "\n"; // = max p[i] trên xâu biến đổi
2. Kiểm tra đoạn có phải palindrome không (0-based):
// Tâm trong xâu biến đổi tương ứng vị trí (l+r+1) (vì mỗi ký tự → 2 vị trí)
// p[l+r+1] >= r-l+1 ⟺ s[l..r] là palindrome
bool is_palindrome(vector<int>& p, int l, int r) {
int center = l + r + 1; // vị trí tâm trong t
return p[center] >= r - l + 1;
}
3. Đếm số palindrome con:
Tổng số palindrome con = (trên xâu biến đổi).
Độ phức tạp
thời gian và bộ nhớ — mỗi ký tự được xét tối đa hai lần (một lần mở rộng, một lần bị bao phủ).
Khi nào dùng Manacher?
- Tìm palindrome dài nhất trong thay vì brute force.
- Kiểm tra nhanh tính palindrome của nhiều đoạn con (kết hợp sparse table).
- Đếm tổng số chuỗi con là palindrome.
Bình luận