Bỏ qua để đến nội dung

Xâu đối xứng, thuật toán Manacher

Mức độ: Nâng cao

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.

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.

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#
i0123456789101112
p0103016103010

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].

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]) // 2
print(s[bat_dau:bat_dau + p[tam]]) # xâu con đối xứng dài nhất
print(sum((x + 1) // 2 for x in p)) # số xâu con đối xứng

Từ mảng p, nhiều câu hỏi trả lời ngay:

Câu hỏiCách tính
Độ dài xâu con đối xứng dài nhấtgiá 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ôngtâ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ấtp[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ấtp[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.

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ố.

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.

Xem đáp số

10

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

xyzzyx

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

1 1 5 1 1 11 1 1 5 1 1

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

32

Hướng dẫn giải chi tiết: liên hệ tác giả.

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ậpIn ra
aaaa
2
6

Kiểm tra: nhập

abaabaabaaba
4
Xem đáp số

15

Hướng dẫn giải chi tiết: liên hệ tác giả.

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ậpIn ra
abacaba
3
1 7
2 4
1 2
YES
NO
NO

Kiểm tra: nhập

aabbaabcbaab
5
1 6
2 5
7 12
8 11
3 10
Xem đáp số
YES
YES
NO
NO
NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bà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.

Xem đáp số

1 2 1 2 3 2 3 4

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

bumbiibmub

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

7

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

78

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

7

Hướng dẫn giải chi tiết: liên hệ tác giả.

Th.S Trần Huy Phúc

Th.S Trần Huy Phúc

Principal Software Engineer @Adnovum & Bumbii Academy