Editorial: Mathematical Algorithms TWK Open ∮ Problem #E - Chuỗi Đối Xứng Cấm

1. Ý tưởng

Ta cần đếm số đoạn con \(S[l..r]\) sao cho:

• \(S[l..r]\) là palindrome.
• \(S[l..r]\) không chứa bất kỳ xâu cấm \(P_i\) nào.

Hai điều kiện này được xử lý bằng hai thuật toán kinh điển:

• Aho–Corasick: xử lý tập xâu cấm.
• Manacher: xử lý tất cả palindrome của \(S\).

Sau khi kết hợp hai cấu trúc này, bài toán còn lại là tìm bán kính palindrome lớn nhất không vượt qua một giới hạn đã biết.

2. Biến điều kiện xâu cấm thành giới hạn bên phải

Với mỗi vị trí bắt đầu \(l\), ta muốn biết vị trí lớn nhất \(r\) sao cho \(S[l..r]\) chưa chứa xâu cấm.

Đặt: \(\qquad maxR[l]\) là vị trí phải lớn nhất mà \(S[l...maxR[l]\) không chứa xâu cấm.

Khi đó: \(\qquad S[l..r]\) hợp lệ \(\Leftrightarrow\) \(r\ \le\ maxR[l]\).

Nếu tìm được \(maxR\) cho mọi \(l\), phần xâu cấm đã được xử lý hoàn toàn.

3. Aho–Corasick

Xây trie chứa toàn bộ \(P_i\) và các liên kết fail.

Tại mỗi node, lưu:

int min_len;

min_len là độ dài nhỏ nhất của một xâu cấm kết thúc tại node đó hoặc tại một node trên đường fail.

Khi xây automaton:
trie[u].min_len=min(trie[u].min_len,trie[trie[u].fail].min_len);

Nhờ vậy, khi đang ở node \(u\) sau khi đọc \(S[i]\), nếu min_len hữu hạn thì tồn tại một xâu cấm kết thúc tại \(i\).

Nếu độ dài nhỏ nhất là \(L\), xâu đó bắt đầu tại: \(\qquad l\ =\ i\ -\ L\ +\ 1\).

Ta lưu:

min_end_at[l] = min(min_end_at[l], i);

Tức là có một xâu cấm bắt đầu tại \(l\) và kết thúc tại \(i\).

4. Từ các xâu cấm đến \(maxR\)

Chỉ xét xâu cấm bắt đầu đúng tại \(l\) là chưa đủ.

Ví dụ một xâu cấm bắt đầu tại \(j>l\) thì nó vẫn nằm trong đoạn \(S[l..r]\) nếu \(r\) đủ lớn.

Vì vậy ta cần xét tất cả \(j\ge l\).

Ta thực hiện suffix minimum:

for (int i = n - 1, cur = n; i >= 0; i--) {
    cur = min(cur, min_end_at[i]);
    max_valid_r[i] = cur - 1;
}

Sau bước này: \(maxR[l]\ =\ \min_{j \ge l}(v_j)\) (vị trí kết thúc của xâu cấm bắt đầu tại j) \(-\ 1\).

Do đó: \(qquad S[l..r]\) không chứa xâu cấm \(\Leftrightarrow\ r\ \le\ maxR[l]\)

Đây là bước then chốt để ghép Aho–Corasick với Manacher.

5. Tìm palindrome bằng Manacher

Ta dùng hai mảng:

d1[i]: bán kính palindrome lẻ tâm tại \(i\).
d2[i]: bán kính palindrome chẵn với tâm nằm giữa \(i-1\) và \(i\).

Palindrome lẻ

Với bán kính \(k\), đoạn palindrome là: \([i\ -\ k\ ,\ i\ +\ k]\)

Ta có: \(0\ \le\ k\ <\ d1[i]\)

Palindrome chẵn

Với bán kính \(k\), đoạn palindrome là: \([i\ -\ k\ ,\ i\ +\ k\ -\ 1]\)

Ta có: \(1\ \le\ k\ \le\ d2[i]\)

Manacher tính toàn bộ d1, d2 trong \(O(n)\).

6. Kiểm tra palindrome

Với palindrome lẻ tâm i, bán kính k là S[i-k..i+k], hợp lệ khi i + k <= maxR[i-k].

Binary search k lớn nhất trong [0, d1[i)-1]. Nếu tìm được best thì cộng best + 1.

Với palindrome chẵn, đoạn là S[i-k..i+k-1], hợp lệ khi i + k - 1 <= maxR[i-k]. Binary search k trong [1, d2[i]], rồi cộng best.

7. Độ phức tạp

Điều kiện hợp lệ theo bán kính là đơn điệu: nếu palindrome bán kính k đã chứa xâu cấm thì mọi palindrome lớn hơn cũng chứa nó, nên có thể binary search.

Đặt L = sum(|P_i|):

• Aho–Corasick: \(O(L)\).
• Manacher: \(O(n)\).
• Binary search: \(O(n\log n)\).

Tổng: \(O(L+n\log n)\).

Bộ nhớ: \(O(L+n)\).

Khi tính maxR, phải xét cả các xâu cấm bắt đầu sau l, không chỉ tại l.