Nổi Bật Trong Đàn

Lời giải: Nổi Bật Trong Đàn

Nhận xét quan trọng

Bài toán yêu cầu với mỗi chuỗi $s_i$, tính tổng độ dài của tất cả xâu con phân biệt của $s_i$ mà không xuất hiện trong bất kỳ $s_j$ nào khác ($j\ne i$).

Số lượng xâu con có thể rất lớn, nên ta cần cấu trúc dữ liệu mạnh để xử lý hiệu quả.

Hướng tiếp cận: Suffix Array

Ý tưởng cốt lõi là nối tất cả $N$ chuỗi lại với nhau bằng các ký tự phân cách (ví dụ ?, |, ...) để tạo thành một chuỗi tổng hợp $S$. Sau đó xây dựng suffix array (mảng hậu tố) và mảng LCP (Longest Common Prefix) cho $S$.

Tại sao Suffix Array?

Suffix array sắp xếp tất cả hậu tố của $S$ theo thứ tự từ điển. Mọi xâu con của $s_i$ đều là tiền tố của một hậu tố bắt đầu trong $s_i$. Vì vậy, ta có thể xác định xâu con nào của $s_i$ cũng xuất hiện trong $s_j$ bằng cách kiểm tra hàng xóm trong suffix array.

Thuật toán

Với mỗi hậu tố $\text{SA}[k]$ thuộc chuỗi $s_i$, gọi $\ell$ là độ dài hậu tố này (tính từ vị trí bắt đầu đến hết $s_i$). Các tiền tố của hậu tố này có độ dài từ 1 đến $\ell$, và tương ứng là các xâu con của $s_i$.

Một tiền tố có độ dài $d$ không độc đáo khi nó xuất hiện trong một chuỗi khác, tức là khi nó là tiền tố chung với một hậu tố thuộc $s_j$ ($j\ne i$). Độ dài phần không độc đáo tối đa là:

$$\text{maxShared}(k)=max(\text{LCP với hàng xóm gần nhất bên trái từ chuỗi khác},\text{LCP với hàng xóm gần nhất bên phải từ chuỗi khác})$$

Vậy hậu tố $\text{SA}[k]$ đóng góp vào kết quả:

$$max(0,\ell -\text{maxShared}(k))$$

Ngoài ra, cần tránh đếm trùng xâu con xuất hiện nhiều lần trong $s_i$: nếu nhiều hậu tố liên tiếp thuộc cùng chuỗi $s_i$ trong suffix array, phần LCP giữa chúng được trừ đi để không tính hai lần.

Chi tiết xử lý nhóm

Các hậu tố liên tiếp trong suffix array thuộc cùng chuỗi $i$ tạo thành một "khối". Khi xử lý khối $[l,r]$ (tất cả từ chuỗi $i$):

• $\text{lmax}$ = LCP với hậu tố ngay trước khối (từ chuỗi khác)
• Duyệt từ trái sang phải qua khối, cập nhật LCP tích lũy
• Đóng góp của hậu tố $j$ trong khối: $max(0,{\ell }_j-max(\text{lmax},\text{LCP}[j]))$
• Cập nhật $\text{lmax}=min(\text{lmax},\text{LCP}[j])$ để đảm bảo không đếm trùng

Độ phức tạp

• Xây dựng suffix array: $O(|S|\log |S|)$ với $|S|\le 2\times {10}^5$
• Duyệt suffix array: $O(|S|)$
• Tổng: $O(|S|\log |S|)$

Ghi chú cài đặt

• Ký tự phân cách phải nhỏ hơn a trong thứ tự ASCII để không ảnh hưởng đến sắp xếp (dùng ? hoặc ký tự có mã ASCII thấp).
• Mảng $A[k]$ lưu cặp (chỉ số chuỗi, độ dài còn lại trong chuỗi đó) cho mỗi vị trí trong $S$.