Thi đấu

Mảng Hậu Tố (Suffix Array) Cơ Bản và Ứng Dụng Xử Lý Chuỗi

Mảng hậu tố (Suffix Array) kết hợp cùng mảng tiền tố chung dài nhất LCP là cấu trúc dữ liệu nền tảng trong xử lý chuỗi cho phép tìm kiếm xâu mẫu và đếm xâu con phân biệt trong thời gian tối ưu.

Mảng Hậu Tố (Suffix Array) Cơ Bản và Ứng Dụng Xử Lý Chuỗi

Trong khoa học máy tính và lập trình thi đấu chuyên nghiệp, xử lý chuỗi (String Processing) luôn là một trong những mảng kiến thức sâu rộng và có tính ứng dụng thực tế cao nhất: từ công cụ tìm kiếm toàn văn (Full-text Search), nén dữ liệu (Burrows-Wheeler Transform) cho đến giải trình tự gen sinh học (Bioinformatics).

Để giải quyết các bài toán hóc búa như:

  • Đếm số lượng chuỗi con phân biệt của một văn bản.
  • Tìm xâu con chung dài nhất giữa nhiều chuỗi ký tự.
  • Tìm vị trí xuất hiện của một từ khóa mẫu (Pattern Matching) với hàng triệu truy vấn trực tuyến.

Cấu trúc Cây hậu tố (Suffix Tree) về mặt lý thuyết đạt độ phức tạp tuyến tính bằng thuật toán Ukkonen nhưng lại cực kỳ phức tạp để cài đặt trong phòng thi và tiêu tốn gấp 20 đến 30 lần bộ nhớ do hệ thống con trỏ dày đặc. Năm 1990, hai nhà khoa học Udi Manber và Gene Myers đã phát minh ra Mảng hậu tố (Suffix Array) — một giải pháp thay thế hoàn hảo: Cài đặt ngắn gọn hơn rất nhiều, tiết kiệm bộ nhớ gấp 4 lần và khi kết hợp với Mảng LCP (Longest Common Prefix) có thể giải quyết hầu hết mọi bài toán của Suffix Tree!

MẢNG HẬU TỐ (SUFFIX ARRAY) & MẢNG LCP Sắp xếp toàn bộ hậu tố theo thứ tự từ điển và tính tiền tố chung dài nhất bằng Kasai trong O(N) Bảng Suffix Array & LCP với s = "banana" HạngSA[i]Xâu hậu tố SuffixLCP[i] 0 5 a 1 1 3 ana 3 2 1 anana 0 3 0 banana 0 4 4 na 2 5 2 nana - SA: [5, 3, 1, 0, 4, 2] • LCP: [1, 3, 0, 0, 2] Đếm số xâu con phân biệt CÔNG THỨC TRÙNG LẶP: Số xâu = N*(N+1)/2 - ∑ LCP[i] Với "banana": 21 - (1+3+0+0+2) = 15Mỗi LCP trừ đi đúng số tiền tố bị trùng! THUẬT TOÁN KASAI O(N): h_mới ≥ h_cũ - 1 Khi dịch sang hậu tố kế tiếp trong xâu,chiều cao h chỉ giảm tối đa 1 đơn vị. ĐỘ PHỨC TẠP TỔNG THỂ:Xây dựng SA: O(N log N) hoặc O(N log² N) • Xây dựng LCP: O(N) • Tìm kiếm xâu mẫu P: O(|P| log N).
MẢNG HẬU TỐ (SUFFIX ARRAY) Sắp xếp xâu hậu tố và mảng LCP Kasai Bảng SA & LCP với s = "banana" i SA[i] Hậu tố Suffix LCP[i] 0 5 a 1 1 3 ana 3 2 1 anana 0 3 0 banana 0 4 4 na 2 5 2 nana - ĐẾM SỐ XÂU CON PHÂN BIỆT: Số xâu = N*(N+1)/2 - ∑ LCP[i] Với "banana": 21 - 6 = 15 xâu Mỗi LCP trừ đi phần tiền tố trùng lặp kề nhau. TÍNH CHẤT KASAI O(N): h_kế_tiếp ≥ h_trước - 1 Đảm bảo tổng số lần so sánh ≤ 2N.
Bảng sắp xếp mảng hậu tố Suffix Array, mảng LCP và công thức đếm số xâu con phân biệt.

Định nghĩa xâu hậu tố và mảng hậu tố

Cho một chuỗi ký tự \(S\) có độ dài \(N\), các ký tự được đánh chỉ số từ \(0\) đến \(N - 1\): \[S = s_0 s_1 \dots s_{N-1}\]

Một xâu hậu tố (Suffix) bắt đầu tại vị trí \(i\) (ký hiệu là \(\text{Suffix}(i)\)) là chuỗi con liên tiếp tính từ ký tự thứ \(i\) cho đến hết chuỗi: \[\text{Suffix}(i) = S[i \dots N - 1]\] Một xâu độ dài \(N\) có đúng \(N\) xâu hậu tố ứng với các chỉ số \(i \in \{0, 1, \dots, N - 1\}\).

Mảng hậu tố Suffix Array (SA) là gì?

Mảng hậu tố \(SA\) là một hoán vị của tập hợp chỉ số \(\{0, 1, \dots, N - 1\}\) đại diện cho danh sách các xâu hậu tố sau khi đã được sắp xếp theo thứ tự từ điển (lexicographical order) tăng dần:

\[\text{Suffix}(SA[0]) \lt \text{Suffix}(SA[1]) \lt \dots \lt \text{Suffix}(SA[N - 1])\]

Ví dụ kinh điển với xâu "banana" (\(N = 6\))

Liệt kê 6 xâu hậu tố ban đầu:

  • \(\text{Suffix}(0) = \text{"banana"}\)
  • \(\text{Suffix}(1) = \text{"anana"}\)
  • \(\text{Suffix}(2) = \text{"nana"}\)
  • \(\text{Suffix}(3) = \text{"ana"}\)
  • \(\text{Suffix}(4) = \text{"na"}\)
  • \(\text{Suffix}(5) = \text{"a"}\)

Sắp xếp 6 xâu này theo thứ tự từ điển tăng dần:

  1. \(\text{"a"} \implies \text{vị trí ban đầu } 5\)
  2. \(\text{"ana"} \implies \text{vị trí ban đầu } 3\)
  3. \(\text{"anana"} \implies \text{vị trí ban đầu } 1\)
  4. \(\text{"banana"} \implies \text{vị trí ban đầu } 0\)
  5. \(\text{"na"} \implies \text{vị trí ban đầu } 4\)
  6. \(\text{"nana"} \implies \text{vị trí ban đầu } 2\)

Do đó, Mảng hậu tố của "banana" là: \[SA = [5, 3, 1, 0, 4, 2]\]

Thuật toán xây dựng mảng hậu tố bằng nhân đôi độ dài Prefix Doubling

Nếu dùng hàm so sánh chuỗi ngây thơ, mỗi phép so sánh hai hậu tố tốn thời gian \(O(N)\). Sắp xếp \(N\) hậu tố sẽ tốn \(O(N^2 \log N)\) — một độ phức tạp hoàn toàn bất khả thi khi \(N \ge 10^5\).

Phương pháp chuẩn mực để xây dựng Suffix Array trong các cuộc thi lập trình là kỹ thuật nhân đôi độ dài (Prefix Doubling) kết hợp gán thứ hạng tương đương (Equivalence Classes): Tại mỗi bước \(k = 0, 1, 2, \dots\): Ta sắp xếp các xâu con có độ dài \(2^k\).

  • Ở bước khởi tạo \(k = 0\): Ta sắp xếp các đoạn con độ dài \(1\) (chính là từng ký tự \(S[i]\)). Gán thứ hạng \(\text{rank}[i]\) cho mỗi vị trí dựa vào mã ASCII của ký tự tương ứng. Các ký tự giống nhau sẽ nhận chung một giá trị rank.
  • Ở bước lặp \(k \ge 1\): Giả sử ta đã có thứ hạng của mọi đoạn con độ dài \(2^{k-1}\). Để so sánh hai đoạn con độ dài \(2^k\) bắt đầu tại vị trí \(i\) và \(j\), ta tách mỗi đoạn con thành hai nửa có cùng độ dài \(2^{k-1}\):
    • Nửa đầu: bắt đầu tại \(i\), có thứ hạng đã biết là \(\text{rank}[i]\).
    • Nửa sau: bắt đầu tại \(i + 2^{k-1}\), có thứ hạng là \(\text{rank}[i + 2^{k-1}]\). Nếu chỉ số này vượt quá độ dài xâu \(N\), ta quy ước gán giá trị \(-1\) (hoặc một số nhỏ hơn mọi rank hợp lệ).
    • Khi đó, việc so sánh hai đoạn con dài \(2^k\) quy về việc so sánh cặp số nguyên hai chiều: \[(\text{rank}[i], \text{rank}[i + 2^{k-1}]) \quad \text{so với} \quad (\text{rank}[j], \text{rank}[j + 2^{k-1}])\]

Vì độ dài đoạn con tăng gấp đôi sau mỗi vòng lặp (\(1, 2, 4, 8, \dots\)), thuật toán chỉ cần thực hiện tối đa \(\lceil \log_2 N \rceil\) bước lặp. Tại mỗi bước:

  • Nếu sử dụng hàm sắp xếp tiêu chuẩn std::sort của C++, mỗi bước tốn \(O(N \log N)\), đưa tổng thời gian toàn thuật toán đạt \(O(N \log^2 N)\). Cài đặt này chỉ tốn khoảng 25 dòng mã nguồn, chạy cực nhanh trong thực tế và đáp ứng tốt giới hạn thời gian 1 giây với \(N \le 2 \cdot 10^5\).
  • Nếu sử dụng thuật toán sắp xếp cơ số Radix Sort (thực hiện Counting Sort hai lượt cho cặp khóa), thời gian của mỗi bước giảm xuống \(O(N)\), giúp tổng thời gian đạt mức tối ưu \(O(N \log N)\).

Mảng tiền tố chung dài nhất LCP và thuật toán Kasai O(N)

Mảng hậu tố tự nó là một công cụ mạnh mẽ, nhưng sức mạnh vượt trội của nó trong các kỳ thi chỉ thực sự phát huy tối đa khi kết hợp cùng Mảng tiền tố chung dài nhất (LCP Array - Longest Common Prefix).

Định nghĩa mảng LCP

Gọi \(LCP[i]\) là độ dài của tiền tố chung dài nhất giữa hai xâu hậu tố đứng kề nhau trong mảng \(SA\): \[LCP[i] = \text{lcp}(\text{Suffix}(SA[i]), \text{Suffix}(SA[i + 1])) \quad (0 \le i \le N - 2)\]

Trong ví dụ chuỗi "banana" với \(SA = [5, 3, 1, 0, 4, 2]\):

  • Giữa \(\text{"a"}\) và \(\text{"ana"}\): tiền tố chung là "a" \(\implies LCP[0] = 1\).
  • Giữa \(\text{"ana"}\) và \(\text{"anana"}\): tiền tố chung là "ana" \(\implies LCP[1] = 3\).
  • Giữa \(\text{"anana"}\) và \(\text{"banana"}\): không có tiền tố chung \(\implies LCP[2] = 0\).
  • Giữa \(\text{"banana"}\) và \(\text{"na"}\): không có tiền tố chung \(\implies LCP[3] = 0\).
  • Giữa \(\text{"na"}\) và \(\text{"nana"}\): tiền tố chung là "na" \(\implies LCP[4] = 2\).

Mảng LCP của "banana" là: \([1, 3, 0, 0, 2]\).

Thuật toán Kasai tính mảng LCP trong thời gian tuyến tính O(N)

Nếu tính LCP cho từng cặp xâu hậu tố kề nhau một cách độc lập, ta có thể mất tới \(O(N^2)\) thời gian trong trường hợp xấu nhất (ví dụ xâu toàn ký tự giống nhau như "aaaaa"). Năm 2001, nhà khoa học Toru Kasai và các cộng sự đã công bố một thuật toán mang tính đột phá:

  • Thay vì duyệt theo thứ tự vị trí xuất hiện trong mảng \(SA\), Kasai duyệt các hậu tố theo thứ tự chỉ số ban đầu trên xâu gốc: \(i = 0, 1, 2, \dots, N - 1\).
  • Để làm được điều này, ta cần mảng nghịch đảo \(\text{inv}[i]\) lưu vị trí của hậu tố thứ \(i\) trong mảng \(SA\) (\(\text{inv}[SA[p]] = p\)).
  • Bổ đề Kasai then chốt: Giả sử hậu tố bắt đầu tại vị trí \(i\) có tiền tố chung dài nhất với hậu tố đứng ngay trước nó trong \(SA\) là \(h\). Khi ta bỏ đi ký tự đầu tiên để chuyển sang xét hậu tố tiếp theo bắt đầu tại \(i + 1\), cả hai hậu tố đều bị cắt ngắn đi đúng 1 ký tự ở đầu. Vì thứ tự từ điển giữa các hậu tố không thay đổi sau khi cắt bỏ tiền tố chung, hậu tố kề trước của \(\text{Suffix}(i + 1)\) trong \(SA\) chắc chắn phải chia sẻ với nó một tiền tố chung có độ dài ít nhất là \(h - 1\): \[h_{\text{mới}} \ge h_{\text{cũ}} - 1\]

Ý nghĩa của bất đẳng thức này vô cùng to lớn: Sau mỗi bước chuyển từ \(i\) sang \(i + 1\), giá trị của \(h\) chỉ có thể giảm đi tối đa 1 đơn vị. Trong khi đó, ở các vòng lặp kiểm tra ký tự tiếp theo, \(h\) chỉ có thể tăng lên. Do \(h\) không bao giờ vượt quá độ dài chuỗi \(N\), tổng số lần tăng của biến \(h\) trong toàn bộ thuật toán bị chặn trên bởi \(2N\). Nhờ đó, thuật toán Kasai tìm được toàn bộ mảng LCP trong đúng thời gian tuyến tính \(O(N)\) với cấu trúc mã nguồn vô cùng gọn gàng!

Ứng dụng trọng tâm trong lập trình thi đấu

1. Đếm số xâu con phân biệt trong O(N log N)

Một bài toán thường xuyên xuất hiện trong các kỳ thi học sinh giỏi quốc gia: Cho chuỗi ký tự \(S\) độ dài \(N\). Hãy đếm số lượng chuỗi con liên tiếp phân biệt (Distinct Substrings) của \(S\).

Tổng số tất cả các xâu con (kể cả những xâu trùng lặp nhau) của một chuỗi độ dài \(N\) là: \[\frac{N(N + 1)}{2}\]

Mỗi chuỗi con bất kỳ của \(S\) thực chất luôn là một tiền tố của một xâu hậu tố nào đó. Khi ta xét duyệt qua các xâu hậu tố theo thứ tự sắp xếp từ điển tăng dần trong mảng \(SA\):

  • Hậu tố \(\text{Suffix}(SA[i])\) có độ dài bằng \(N - SA[i]\), do đó nó có thể đóng góp tối đa \(N - SA[i]\) chuỗi con tiền tố.
  • Tuy nhiên, trong số các chuỗi con tiền tố này, có đúng \(LCP[i - 1]\) chuỗi con đã từng xuất hiện ở các hậu tố đứng trước nó. Do mảng \(SA\) đã được sắp xếp theo thứ tự từ điển, mọi chuỗi con trùng lặp luôn xuất hiện tập trung ở hậu tố kề ngay phía trước.
  • Vì vậy, số lượng chuỗi con mới chưa từng xuất hiện mà hậu tố \(\text{Suffix}(SA[i])\) thực sự mang lại là: \[(N - SA[i]) - LCP[i - 1]\]

Lấy tổng tích lũy trên toàn bộ \(N\) hậu tố từ đầu đến cuối, ta thu được công thức tổng quát tuyệt đẹp: \[\text{Số chuỗi con phân biệt} = \frac{N(N + 1)}{2} - \sum_{i=0}^{N-2} LCP[i]\]

2. Tìm kiếm xâu mẫu Pattern Matching bằng tìm kiếm nhị phân

Cho một văn bản tĩnh \(S\) độ dài \(N\) và \(Q\) truy vấn, mỗi truy vấn cung cấp một xâu mẫu \(P\) độ dài \(M\). Yêu cầu kiểm tra xem \(P\) có xuất hiện trong \(S\) hay không và đếm số lần xuất hiện.

Vì mọi lần xuất hiện của \(P\) trong \(S\) đều tương đương với việc \(P\) là tiền tố của một xâu hậu tố nào đó, và danh sách các xâu hậu tố trong \(SA\) đã được sắp thứ tự từ điển:

  • Tất cả các hậu tố bắt đầu bằng chuỗi \(P\) sẽ nằm liên tiếp nhau tạo thành một đoạn \([L, R]\) trên mảng \(SA\).
  • Ta có thể thực hiện tìm kiếm nhị phân hai lần (tương tự std::lower_bound và std::upper_bound) để xác định biên trái \(L\) và biên phải \(R\). Mỗi phép so sánh chuỗi trong tìm kiếm nhị phân tốn \(O(M)\).
  • Do đó, thời gian trả lời mỗi truy vấn là \(O(M \log N)\). Nếu kết hợp thêm kỹ thuật LCP và bảng thưa Sparse Table, thời gian có thể tối ưu sâu hơn xuống còn \(O(M + \log N)\).

3. Tìm LCP giữa hai hậu tố bất kỳ bằng bài toán RMQ

LCP giữa hai hậu tố bất kỳ ở vị trí \(i\) và \(j\) trong mảng \(SA\) (\(i \lt j\)) chính là giá trị nhỏ nhất của mảng LCP trong đoạn từ \(i\) đến \(j - 1\): \[\text{LCP}(SA[i], SA[j]) = \min_{k=i}^{j-1} LCP[k]\] Đây chính là bài toán Range Minimum Query (RMQ) kinh điển. Bằng cách tiền xử lý mảng LCP bằng Bảng thưa (Sparse Table) trong thời gian \(O(N \log N)\), ta có thể truy vấn tiền tố chung dài nhất giữa hai vị trí bất kỳ trên chuỗi ban đầu trong đúng thời gian \(O(1)\)!

Học cùng giảng viên

Chủ đề này nằm trong Buổi 09 - KMP, Z-function, Trie & Rolling Hash của Tài năng lập trình. Xem đề cương

Hướng dẫn từng bước xây dựng Prefix Doubling qua bảng mô phỏng

Để hiểu tường minh cách thuật toán Prefix Doubling vận hành, ta hãy theo dõi chi tiết quá trình xử lý từng bước trên xâu mẫu \(S = \text{"banana"}\) có độ dài \(N = 6\):

Vòng lặp k = 0: Độ dài đoạn con là 1

Ở bước này, mỗi vị trí \(i\) đại diện cho một ký tự đơn lẻ \(S[i]\):

  • Các ký tự gồm: \(S[0] = \text{'b'}, S[1] = \text{'a'}, S[2] = \text{'n'}, S[3] = \text{'a'}, S[4] = \text{'n'}, S[5] = \text{'a'}\).
  • Thứ tự sắp xếp các ký tự này theo bảng chữ cái: 'a' nhỏ nhất (xuất hiện ở các vị trí 1, 3, 5), tiếp theo là 'b' (vị trí 0), và lớn nhất là 'n' (vị trí 2, 4).
  • Gán thứ hạng tương đương (Equivalence Rank):
    • Các vị trí có ký tự 'a' nhận rank bằng \(0\): \(\text{rank}[1] = 0, \text{rank}[3] = 0, \text{rank}[5] = 0\).
    • Vị trí có ký tự 'b' nhận rank bằng \(1\): \(\text{rank}[0] = 1\).
    • Các vị trí có ký tự 'n' nhận rank bằng \(2\): \(\text{rank}[2] = 2, \text{rank}[4] = 2\).
  • Mảng thứ hạng sau vòng lặp \(k = 0\) là: \(\text{rank} = [1, 0, 2, 0, 2, 0]\).

Vòng lặp k = 1: Độ dài đoạn con là 2

Mỗi đoạn con độ dài 2 bắt đầu tại vị trí \(i\) được ghép từ hai nửa độ dài 1: ký tự tại \(i\) và ký tự tại \(i + 1\). Khóa sắp xếp của mỗi vị trí \(i\) là cặp \((\text{rank}[i], \text{rank}[i + 1])\):

  • Vị trí 0: cặp khóa \((1, 0)\), tương ứng xâu "ba".
  • Vị trí 1: cặp khóa \((0, 2)\), tương ứng xâu "an".
  • Vị trí 2: cặp khóa \((2, 0)\), tương ứng xâu "na".
  • Vị trí 3: cặp khóa \((0, 2)\), tương ứng xâu "an".
  • Vị trí 4: cặp khóa \((2, 0)\), tương ứng xâu "na".
  • Vị trí 5: ký tự cuối cùng, không có ký tự tiếp theo, ta gán khóa thứ hai là \(-1\): cặp khóa \((0, -1)\), tương ứng xâu "a".

Sắp xếp các cặp khóa này theo thứ tự từ điển:

  1. Vị trí 5 với cặp \((0, -1) \implies \text{rank mới} = 0\).
  2. Vị trí 1 và vị trí 3 với cặp \((0, 2) \implies \text{cùng nhận rank mới} = 1\).
  3. Vị trí 0 với cặp \((1, 0) \implies \text{rank mới} = 2\).
  4. Vị trí 2 và vị trí 4 với cặp \((2, 0) \implies \text{cùng nhận rank mới} = 3\).

Mảng thứ hạng sau vòng lặp \(k = 1\) trở thành: \(\text{rank} = [2, 1, 3, 1, 3, 0]\).

Vòng lặp k = 2: Độ dài đoạn con là 4

Mỗi đoạn con độ dài 4 được ghép từ hai nửa độ dài 2: nửa đầu tại \(i\) và nửa sau tại \(i + 2\). Khóa sắp xếp là cặp \((\text{rank}[i], \text{rank}[i + 2])\):

  • Vị trí 5: cặp \((0, -1) \implies\) rank 0.
  • Vị trí 3: cặp \((1, 0) \implies\) rank 1 (xâu "ana").
  • Vị trí 1: cặp \((1, 1) \implies\) rank 2 (xâu "anan").
  • Vị trí 0: cặp \((2, 3) \implies\) rank 3 (xâu "bana").
  • Vị trí 4: cặp \((3, -1) \implies\) rank 4 (xâu "na").
  • Vị trí 2: cặp \((3, 3) \implies\) rank 5 (xâu "nana").

Tại thời điểm này, tất cả 6 giá trị rank đều phân biệt hoàn toàn (từ 0 đến 5). Khi không còn bất kỳ sự trùng lặp rank nào, thứ tự sắp xếp của toàn bộ các xâu hậu tố đã được xác định tuyệt đối, thuật toán có thể dừng sớm ngay lập tức mà không cần chạy tiếp các bước \(k\) tiếp theo. Kết quả hoán vị cuối cùng chính là mảng hậu tố \(SA = [5, 3, 1, 0, 4, 2]\).

Các bẫy thường gặp và kỹ thuật tối ưu trong phòng thi

Khi triển khai Mảng hậu tố trong môi trường áp lực thời gian của các kỳ thi quốc tế, lập trình viên thường mắc phải một số sai lầm kinh điển sau:

  1. Xử lý chỉ số tràn biên ngoài độ dài chuỗi: Khi tính khóa nửa sau \(i + 2^{k-1}\), nếu vượt quá chỉ số \(N - 1\), bắt buộc phải gán một giá trị nhỏ hơn mọi thứ hạng hợp lệ (thường chọn \(-1\) hoặc \(0\) nếu các thứ hạng thực tế được đánh số từ \(1\)). Nếu không kiểm tra cẩn thận, chương trình sẽ truy cập ngoài bộ nhớ hợp lệ gây lỗi Runtime Error (Segmentation Fault).
  2. Sai lầm khi so sánh bằng kiểu số thực: Tuyệt đối không quy đổi chuỗi hoặc thứ hạng thành số thực để so sánh vì số thực có hiện tượng mất độ chính xác (Precision Error). Luôn so sánh trực tiếp các cặp số nguyên.
  3. Tối ưu tốc độ sắp xếp bằng kỹ thuật Bitwise Packing: Trong C++, việc sử dụng std::pair có thể làm chậm tốc độ do cấp phát và sao chép dữ liệu. Một mẹo tối ưu cực mạnh được các cao thủ CP sử dụng là gom hai số nguyên 32-bit vào một số nguyên không dấu 64-bit uint64_t: \[\text{key} = ((\mathrm{uint64\_t})\text{rank1} \ll 32) \mid (\mathrm{uint32\_t})(\text{rank2} + 1)\] Phải cộng 1 vào rank2 trước khi ép kiểu: giá trị \(-1\) của nửa sau vượt biên thành \(0\), vẫn nhỏ hơn mọi rank. Nếu ép thẳng, \(-1\) thành \(2^{32} - 1\), lớn hơn mọi rank, và xâu "banana" sẽ cho mảng hậu tố sai \([1, 3, 5, 0, 2, 4]\) thay vì \([5, 3, 1, 0, 4, 2]\). Khi đó, việc so sánh cặp khóa chỉ đơn thuần là phép so sánh một số nguyên 64-bit duy nhất, tăng tốc độ chạy của hàm std::sort lên gấp 2 đến 3 lần!
  4. Không khởi tạo lại mảng khi xử lý nhiều test case: Trong các bài toán có nhiều bộ kiểm thử liên tiếp (\(T\) test cases), việc quên xóa hoặc thiết lập lại kích thước các mảng toàn cục sa, lcp, rank_arr sẽ dẫn đến việc dữ liệu của test trước tràn sang làm sai kết quả của test sau.

Cài đặt chuẩn C++17 và Python 3

Dưới đây là lời giải hoàn chỉnh được kiểm thử kỹ lưỡng, xây dựng Suffix Array và mảng LCP theo thuật toán Kasai:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>

using namespace std;

// Cấu trúc Mảng hậu tố (Suffix Array) và mảng LCP (Thuật toán Kasai)
// Độ phức tạp thời gian xây dựng: O(N log^2 N) hoặc O(N log N)
// Tính mảng LCP: Tuyến tính O(N)
struct SuffixArray {
    string s;
    int n;
    vector<int> sa;
    vector<int> lcp;
    vector<int> rank_arr;

    SuffixArray(const string& str) : s(str), n(str.size()) {
        build_sa();
        build_lcp();
    }

    void build_sa() {
        sa.resize(n);
        iota(sa.begin(), sa.end(), 0);
        rank_arr.resize(n);
        for (int i = 0; i < n; i++) rank_arr[i] = (unsigned char)s[i];

        vector<int> tmp_rank(n);
        for (int k = 0; (1 << k) < n; k++) {
            int shift = 1 << k;
            auto compare_key = [&](int i, int j) {
                if (rank_arr[i] != rank_arr[j]) return rank_arr[i] < rank_arr[j];
                int ri = (i + shift < n) ? rank_arr[i + shift] : -1;
                int rj = (j + shift < n) ? rank_arr[j + shift] : -1;
                return ri < rj;
            };

            sort(sa.begin(), sa.end(), compare_key);

            tmp_rank[sa[0]] = 0;
            for (int i = 1; i < n; i++) {
                tmp_rank[sa[i]] = tmp_rank[sa[i - 1]] + (compare_key(sa[i - 1], sa[i]) ? 1 : 0);
            }
            rank_arr = tmp_rank;
            if (rank_arr[sa[n - 1]] == n - 1) break;
        }
    }

    // Thuật toán Kasai tính mảng LCP trong O(N)
    void build_lcp() {
        if (n <= 1) return;
        vector<int> inv_sa(n);
        for (int i = 0; i < n; i++) inv_sa[sa[i]] = i;

        lcp.assign(n - 1, 0);
        int h = 0;
        for (int i = 0; i < n; i++) {
            if (inv_sa[i] > 0) {
                int j = sa[inv_sa[i] - 1];
                while (i + h < n && j + h < n && s[i + h] == s[j + h]) {
                    h++;
                }
                lcp[inv_sa[i] - 1] = h;
                if (h > 0) h--;
            }
        }
    }

    // Đếm số lượng xâu con phân biệt của s: N*(N+1)/2 - sum(LCP)
    long long count_distinct_substrings() {
        long long total = (long long)n * (n + 1) / 2;
        long long sum_lcp = 0;
        for (int x : lcp) sum_lcp += x;
        return total - sum_lcp;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    if (!(cin >> s)) return 0;

    SuffixArray sa_solver(s);

    // Dòng 1: Mảng SA
    for (int i = 0; i < sa_solver.n; i++) {
        cout << sa_solver.sa[i] << (i + 1 == sa_solver.n ? "" : " ");
    }
    cout << "\n";

    // Dòng 2: Mảng LCP
    for (int i = 0; i < (int)sa_solver.lcp.size(); i++) {
        cout << sa_solver.lcp[i] << (i + 1 == (int)sa_solver.lcp.size() ? "" : " ");
    }
    cout << "\n";

    // Dòng 3: Số xâu con phân biệt
    cout << sa_solver.count_distinct_substrings() << "\n";

    return 0;
}

Đánh giá độ phức tạp và so sánh cấu trúc

Tiêu chí so sánh Mảng hậu tố (Suffix Array) Cây hậu tố (Suffix Tree) Tự động Suffix (SAM)
Thời gian xây dựng \(O(N \log N)\) hoặc \(O(N \log^2 N)\) \(O(N)\) (Ukkonen) \(O(N \cdot |\Sigma|)\)
Dung lượng bộ nhớ Rất nhỏ (\(4N\) đến \(8N\) bytes) Rất lớn (\(20N\) đến \(40N\) bytes) Trung bình (\(15N\) đến \(25N\) bytes)
Độ phức tạp cài đặt Ngắn gọn, dễ nhớ (khoảng 30 dòng) Cực kỳ phức tạp, dễ lỗi Ngắn gọn nhưng tư duy đồ thị trừu tượng
Truy vấn LCP tùy ý \(O(1)\) khi dùng Sparse Table \(O(1)\) qua bài toán LCA Không hỗ trợ trực tiếp
Ứng dụng thi đấu Phổ biến nhất trong các kỳ thi HSG, ICPC Hiếm khi cài đặt trực tiếp Tối ưu cho bài toán đếm đường đi đồ thị

Luyện ngay trên Big-O Coding

Để nắm vững kỹ thuật mảng hậu tố và giải quyết các bài toán chuỗi hóc búa, bạn hãy thực hành ngay các bài tập sau trên hệ thống Big-O Coding:

Làm thế nào để tìm kiếm sự xuất hiện của xâu mẫu P trong văn bản S bằng Suffix Array?

Vì mảng \(SA\) đã sắp xếp các hậu tố theo thứ tự từ điển, tất cả các hậu tố có tiền tố trùng khớp với \(P\) sẽ nằm ở một đoạn liên tiếp \([L, R]\) trên mảng \(SA\). Bạn chỉ cần thực hiện tìm kiếm nhị phân hai lần để tìm vị trí đầu tiên và vị trí cuối cùng thỏa mãn, thời gian truy vấn là \(O(|P| \log N)\).

LCP giữa hai hậu tố bất kỳ (không nhất thiết kề nhau) được tính như thế nào?

Độ dài tiền tố chung dài nhất giữa hai hậu tố ở chỉ số \(i\) và \(j\) trong mảng \(SA\) (\(i \lt j\)) chính là giá trị nhỏ nhất của mảng LCP trong đoạn từ \(i\) đến \(j - 1\): \(\min_{k=i}^{j-1} LCP[k]\). Bằng cách xây dựng Bảng thưa (Sparse Table) trên mảng LCP trong \(O(N \log N)\), bạn có thể trả lời truy vấn LCP giữa hai vị trí bất kỳ trong \(O(1)\).

Ký tự đặc biệt kết thúc chuỗi có vai trò gì trong việc xây dựng Suffix Array?

Trong nhiều tài liệu, người ta thường thêm ký tự đặc biệt như $ vào cuối chuỗi với quy ước mã ASCII của nó nhỏ hơn mọi ký tự trong bảng chữ cái. Ký tự này đảm bảo không có hậu tố nào là tiền tố thực sự của một hậu tố khác, giúp việc so sánh từ điển luôn dứt khoát và việc ghép nhiều chuỗi để tìm xâu con chung trở nên dễ dàng.

Nguồn tham khảo

Muốn học bài bản cùng giảng viên?

Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.

Xem Tài năng lập trình

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483