Xâu đối xứng, thuật toán Manacher
Xâu đối xứng (palindrome) là xâu đọc xuôi hay đọc ngược đều như nhau: aba, abba, racecar. Đề thi hay hỏi:
xâu con đối xứng dài nhất là gì, có bao nhiêu xâu con đối xứng, đoạn từ l đến r có đối xứng không.
Cách làm từ tâm
Phần tiêu đề “Cách làm từ tâm”Mỗi xâu đối xứng có một tâm: tâm của aba là chữ b, tâm của abba nằm giữa hai chữ b. Từ mỗi tâm, mở rộng
sang hai bên khi hai ký tự hai bên còn bằng nhau, ta được xâu đối xứng dài nhất có tâm đó.
Xâu dài n có 2n - 1 tâm. Với xâu aaaa...a, tâm ở giữa mở rộng được khoảng n/2 bước, nên cả bài mất khoảng
n2/4 bước. Với n = 106 là khoảng 2,5 × 1011 bước.
Manacher làm cùng việc đó trong khoảng 2n bước, nhờ dùng lại kết quả của các tâm đã tính.
Chèn ký tự # để gộp chẵn và lẻ
Phần tiêu đề “Chèn ký tự # để gộp chẵn và lẻ”Xâu đối xứng độ dài lẻ có tâm là một ký tự, độ dài chẵn có tâm nằm giữa hai ký tự. Để chỉ phải xử lý một loại,
chèn ký tự # vào giữa mọi cặp ký tự và vào hai đầu: abaaba thành #a#b#a#a#b#a#. Khi đó mọi xâu đối xứng
đều có tâm là một ký tự của xâu mới t (tâm của abba là dấu # ở giữa).
Gọi p[i] là bán kính lớn nhất: t[i - p[i] .. i + p[i]] đối xứng. Điều hay là p[i] đúng bằng độ dài
xâu đối xứng tương ứng trong xâu gốc, vì trong mỗi bên của t có p[i] ký tự, khoảng một nửa là #.
| t | # | a | # | b | # | a | # | a | # | b | # | a | # |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| p | 0 | 1 | 0 | 3 | 0 | 1 | 6 | 1 | 0 | 3 | 0 | 1 | 0 |
p[6] = 6: cả xâu abaaba (độ dài 6) đối xứng với tâm là dấu # ở vị trí 6. p[3] = 3: aba có tâm là chữ b.
Đổi ngược về xâu gốc s (đánh số từ 0): xâu đối xứng ứng với tâm i bắt đầu ở vị trí (i - p[i]) ÷ 2 và dài p[i].
Dùng lại ảnh đối xứng
Phần tiêu đề “Dùng lại ảnh đối xứng”Giả sử đã biết một đoạn đối xứng [l, r] trong t, với r lớn nhất trong các đoạn đã tìm. Xét tâm i nằm trong đoạn đó (i nhỏ hơn r). Vì [l, r] đối xứng, phần quanh i giống hệt phần quanh ảnh j = l + r - i ở nửa bên kia, nên:
- bán kính tại i ít nhất bằng min(p[j], r - i) (giới hạn r - i vì sau r chưa biết gì);
- chỉ cần so tiếp các ký tự sau r.
Ví dụ với bảng trên: sau tâm 6 đã biết [l, r] = [0, 12]. Tới i = 9, ảnh là j = 0 + 12 - 9 = 3, p[3] = 3 và r - i = 3, nên p[9] ít nhất là 3. Thử mở rộng tiếp thì t[5] và t[13] (không tồn tại), dừng: p[9] = 3, không phải so lại 3 cặp ký tự đầu.
Vì sao chỉ khoảng 2n bước? Mỗi lần so thành công một cặp ký tự ở ngoài r, đoạn [l, r] mới vươn xa hơn, nên r tăng. r chỉ tăng, không quá độ dài t là 2n + 1, nên tổng số lần so thành công không quá 2n + 1. Mỗi tâm có thêm nhiều nhất một lần so thất bại.
def ban_kinh_doi_xung(s): """Chèn '#' vào s được t; trả về p với p[i] là bán kính đối xứng lớn nhất tại t[i] (cũng là độ dài xâu đối xứng tương ứng trong s).""" t = '#' + '#'.join(s) + '#' m = len(t) p = [0] * m l = r = 0 # [l, r]: đoạn đối xứng có r lớn nhất đã biết for i in range(m): if i < r: p[i] = min(r - i, p[l + r - i]) # dùng lại kết quả của ảnh j = l + r - i while i - p[i] - 1 >= 0 and i + p[i] + 1 < m and t[i - p[i] - 1] == t[i + p[i] + 1]: p[i] += 1 if i + p[i] > r: l, r = i - p[i], i + p[i] return p
s = input().strip()p = ban_kinh_doi_xung(s)tam = max(range(len(p)), key=lambda i: p[i])bat_dau = (tam - p[tam]) // 2print(s[bat_dau:bat_dau + p[tam]]) # xâu con đối xứng dài nhấtprint(sum((x + 1) // 2 for x in p)) # số xâu con đối xứng#include <iostream>#include <string>#include <vector>#include <algorithm>using namespace std;
// Chèn '#' vào s được t; p[i] là bán kính đối xứng lớn nhất tại t[i]// (cũng là độ dài xâu đối xứng tương ứng trong s).vector<int> banKinhDoiXung(const string &s) { string t = "#"; for (char c : s) { t += c; t += '#'; } int m = t.size(); vector<int> p(m, 0); for (int i = 0, l = 0, r = 0; i < m; i++) { if (i < r) p[i] = min(r - i, p[l + r - i]); // dùng lại kết quả của ảnh while (i - p[i] - 1 >= 0 && i + p[i] + 1 < m && t[i - p[i] - 1] == t[i + p[i] + 1]) p[i]++; if (i + p[i] > r) l = i - p[i], r = i + p[i]; } return p;}
int main() { string s; cin >> s; vector<int> p = banKinhDoiXung(s); int tam = max_element(p.begin(), p.end()) - p.begin(); cout << s.substr((tam - p[tam]) / 2, p[tam]) << '\n'; // xâu con đối xứng dài nhất long long soXau = 0; for (int x : p) soXau += (x + 1) / 2; cout << soXau << '\n'; // số xâu con đối xứng return 0;}Đọc kết quả từ bán kính
Phần tiêu đề “Đọc kết quả từ bán kính”Từ mảng p, nhiều câu hỏi trả lời ngay:
| Câu hỏi | Cách tính |
|---|---|
| Độ dài xâu con đối xứng dài nhất | giá trị lớn nhất của p |
| Số xâu con đối xứng có tâm i | (p[i] + 1) ÷ 2 (phần nguyên): tâm i có các xâu dài p[i], p[i] - 2, … |
| Đoạn s[l..r] (đánh số từ 0) có đối xứng không | tâm của đoạn trong t là l + r + 1, đoạn đối xứng khi p[l + r + 1] ≥ r - l + 1 |
| Tiền tố đối xứng dài nhất | p[i] lớn nhất trong các tâm có i - p[i] = 0 (chạm đầu t) |
| Hậu tố đối xứng dài nhất | p[i] lớn nhất trong các tâm có i + p[i] = 2n (chạm cuối t) |
Ví dụ số xâu con đối xứng của abaaba: cộng (p[i] + 1) ÷ 2 theo bảng trên được
0 + 1 + 0 + 2 + 0 + 1 + 3 + 1 + 0 + 2 + 0 + 1 + 0 = 11: sáu xâu một chữ, aa, aba (hai lần), baab, abaaba.
Xâu đối xứng cũng làm được bằng hash xâu kết hợp tìm kiếm nhị phân bán kính (khoảng n log n bước). Manacher nhanh hơn và không có rủi ro trùng hash.
Luyện tập
Phần tiêu đề “Luyện tập”Gồm 12 bài, chia thành 3 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.
Nhóm 1. Bán kính đối xứng
Phần tiêu đề “Nhóm 1. Bán kính đối xứng”Bài 1. Độ dài xâu con đối xứng dài nhất
Phần tiêu đề “Bài 1. Độ dài xâu con đối xứng dài nhất”Nhập xâu s gồm chữ cái thường (1 ≤ |s| ≤ 106). In ra độ dài xâu con (gồm các ký tự liên tiếp) đối xứng dài nhất của s.
Ví dụ: nhập babad thì in ra 3.
Kiểm tra: nhập forgeeksskeegfor.
Bài 2. In xâu con đối xứng dài nhất
Phần tiêu đề “Bài 2. In xâu con đối xứng dài nhất”Nhập xâu s gồm chữ cái thường (1 ≤ |s| ≤ 106). In ra xâu con đối xứng dài nhất của s. Nếu có nhiều xâu cùng độ dài lớn nhất, in xâu bắt đầu sớm nhất.
Ví dụ: nhập babad thì in ra bab.
Kiểm tra: nhập abacdfgdcabaxyzzyx.
Bài 3. Đối xứng lẻ tại mỗi ký tự
Phần tiêu đề “Bài 3. Đối xứng lẻ tại mỗi ký tự”Nhập xâu s gồm chữ cái thường (1 ≤ |s| ≤ 106). Với mỗi vị trí i từ 1 đến |s|, in ra độ dài xâu con đối xứng dài nhất có tâm là ký tự thứ i (xâu độ dài lẻ, ký tự thứ i ở chính giữa).
Ví dụ: nhập abacaba thì in ra 1 3 1 7 1 3 1.
Kiểm tra: nhập aabaacaabaa.
Bài 4. Đếm xâu con đối xứng
Phần tiêu đề “Bài 4. Đếm xâu con đối xứng”Nhập xâu s gồm chữ cái thường (1 ≤ |s| ≤ 106). Đếm số cặp (l, r) với 1 ≤ l ≤ r ≤ |s| mà đoạn từ ký tự l đến ký tự r đối xứng (hai đoạn giống nhau ở hai chỗ khác nhau tính là hai).
Ví dụ: nhập aaa thì in ra 6.
Kiểm tra: nhập abacabadabacaba.
Nhóm 2. Đếm và trả lời câu hỏi
Phần tiêu đề “Nhóm 2. Đếm và trả lời câu hỏi”Bài 5. Đếm xâu đối xứng đủ dài
Phần tiêu đề “Bài 5. Đếm xâu đối xứng đủ dài”Dòng đầu là xâu s gồm chữ cái thường (1 ≤ |s| ≤ 106), dòng thứ hai là số K (1 ≤ K ≤ |s|). Đếm số đoạn đối xứng của s có độ dài từ K trở lên (hai đoạn ở hai chỗ khác nhau tính là hai).
Ví dụ:
| Nhập | In ra |
|---|---|
aaaa2 | 6 |
Kiểm tra: nhập
abaabaabaaba4Bài 6. Đoạn này có đối xứng không?
Phần tiêu đề “Bài 6. Đoạn này có đối xứng không?”Dòng đầu là xâu s gồm chữ cái thường (1 ≤ |s| ≤ 106), dòng thứ hai có q (1 ≤ q ≤ 105), q dòng sau mỗi dòng có l, r (1 ≤ l ≤ r ≤ |s|). Với mỗi câu hỏi, in YES nếu đoạn từ ký tự l đến ký tự r đối xứng, ngược lại in NO.
Ví dụ:
| Nhập | In ra |
|---|---|
abacaba31 72 41 2 | YESNONO |
Kiểm tra: nhập
aabbaabcbaab51 62 57 128 113 10Bài 7. Số xâu đối xứng kết thúc tại mỗi vị trí
Phần tiêu đề “Bài 7. Số xâu đối xứng kết thúc tại mỗi vị trí”Nhập xâu s gồm chữ cái thường (1 ≤ |s| ≤ 106). Với mỗi vị trí i từ 1 đến |s|, in ra số đoạn đối xứng của s kết thúc tại ký tự thứ i.
Ví dụ: nhập abba thì in ra 1 1 2 2.
Kiểm tra: nhập aabaabaa.
Bài 8. Thêm vào cuối ít ký tự nhất
Phần tiêu đề “Bài 8. Thêm vào cuối ít ký tự nhất”Nhập xâu s gồm chữ cái thường (1 ≤ |s| ≤ 106). Thêm ít ký tự nhất vào cuối s để được một xâu đối xứng. In ra xâu đối xứng thu được.
Ví dụ: nhập abcb thì in ra abcba.
Kiểm tra: nhập bumbii.
Nhóm 3. Vận dụng
Phần tiêu đề “Nhóm 3. Vận dụng”Bài 9. Cắt thành ít đoạn đối xứng nhất
Phần tiêu đề “Bài 9. Cắt thành ít đoạn đối xứng nhất”Nhập xâu s gồm chữ cái thường (1 ≤ |s| ≤ 2000). Cắt s thành các đoạn liên tiếp sao cho mỗi đoạn đều đối xứng. In ra số đoạn ít nhất.
Ví dụ: nhập abaab thì in ra 2.
Kiểm tra: nhập bananaracecarxyx.
Bài 10. Ghép hai đoạn đối xứng
Phần tiêu đề “Bài 10. Ghép hai đoạn đối xứng”Nhập xâu s gồm chữ cái thường (2 ≤ |s| ≤ 106). Tìm đoạn dài nhất của s mà cắt được thành hai phần khác rỗng, phần nào cũng đối xứng. In ra độ dài đoạn đó.
Ví dụ: nhập abacc thì in ra 5.
Kiểm tra: nhập xabaxxcdcabba.
Bài 11. Cặp đoạn đối xứng không chồng nhau
Phần tiêu đề “Bài 11. Cặp đoạn đối xứng không chồng nhau”Nhập xâu s gồm chữ cái thường (1 ≤ |s| ≤ 106). Đếm số bộ (a, b, x, y) với 1 ≤ a ≤ b nhỏ hơn x ≤ y ≤ |s| mà đoạn a..b và đoạn x..y đều đối xứng. In ra số đó chia lấy dư 109 + 7.
Ví dụ: nhập aaa thì in ra 5.
Kiểm tra: nhập abacabaab.
Bài 12. Đối xứng dài nhất trên vòng tròn
Phần tiêu đề “Bài 12. Đối xứng dài nhất trên vòng tròn”Xâu s (chữ cái thường, 1 ≤ |s| ≤ 106) được viết quanh một vòng tròn: sau ký tự cuối là ký tự đầu. Một đoạn là một số ký tự liên tiếp trên vòng (không quá |s| ký tự). In ra độ dài đoạn đối xứng dài nhất.
Ví dụ: nhập aabca thì in ra 3.
Kiểm tra: nhập cabaxyzyxac.