Lesson 44 — Cấu trúc hậu tố

Ba module tương tác: xây Suffix Array (liệt kê hậu tố rồi sort), LCP array (tiền tố chung của hậu tố kề), và đếm substring phân biệt bằng công thức SA + LCP.

Module 1 — Suffix Array builder

Nhập chuỗi (mặc định "banana"). Bấm Liệt kê để sinh các hậu tố theo vị trí gốc, rồi Sort để sắp xếp theo thứ tự từ điển thành Suffix Array.

Chuỗi:

Bấm "Liệt kê hậu tố" để bắt đầu.

Module 2 — LCP array (Kasai)

Dùng SA đã sort, tính lcp[k] = tiền tố chung dài nhất của suf(sa[k]) và suf(sa[k-1]). Phần chung được tô vàng.

Module này dùng chuỗi của Module 1. Bấm "Tính LCP".

k	sa[k]	suf(sa[k])	lcp[k]

Module 3 — Đếm substring phân biệt

Áp dụng công thức Σ(n − sa[k]) − Σ lcp[k]. Bấm để cộng dồn từng hậu tố và xem tổng.

Cần SA + LCP từ Module 2 trước (hoặc bấm nút này sẽ tự tính).

distinct = Σ (n − sa[k]) − Σ lcp[k]

k	sa[k]	n − sa[k]	lcp[k]	cộng dồn