Máy tự động hậu tố Suffix Automaton (SAM) đếm số xâu con phân biệt

Mục tiêu kiến thức

• Hiểu cấu trúc Máy tự động hậu tố (Suffix Automaton - SAM): Đồ thị có hướng không chu trình (DAG) biểu diễn toàn bộ các xâu con của một chuỗi trong O(N) trạng thái và O(N) cạnh chuyển tiếp.
• Cài đặt hàm sam_extend mở rộng từng ký tự trực tuyến (Online Construction).
• Đếm số lượng xâu con phân biệt của xâu S bằng công thức: ∑ (len[u] - len[link[u]]) trong O(N).

Mô tả bài toán

Cho một xâu ký tự S gồm N chữ cái thường tiếng Anh ('a' đến 'z'). Hãy đếm số lượng xâu con liên tiếp phân biệt (Distinct Substrings) xuất hiện trong S.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ |S| ≤ 10⁶.
• Thời gian chạy: 1000ms.
• Bộ nhớ tối đa: 256MB.