Đếm Xâu Con Khác Nhau · canuc80k6205

Một xâu con liên tiếp của xâu $S$ được tạo bằng cách chọn một đoạn không rỗng gồm các ký tự liên tiếp của $S$ . Hai đoạn nằm ở vị trí khác nhau nhưng có cùng dãy ký tự được xem là cùng một xâu con.

Hãy đếm số xâu con liên tiếp phân biệt theo nội dung của $S$ .

Input

Dòng duy nhất chứa xâu $S$ .

Output

In một số nguyên: số xâu con liên tiếp phân biệt của $S$ .

Constraints

$1 \leq ∣ S ∣ \leq 1 0^{5}$ .
$S$ chỉ gồm các chữ cái thường tiếng Anh từ $a$ đến $z$ .
Chỉ xét các xâu con không rỗng.

Scoring

Subtask $1$ ( $50%$ số điểm): $∣ S ∣ \leq 2000$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

ababa

Output

Giải thích: Các xâu con phân biệt là $a$ , ab, aba, abab, ababa, $b$ , ba, bab và baba, nên đáp án bằng $9$ .

Ý tưởng: Dựng suffix array của S và mảng LCP giữa mỗi hậu tố với hậu tố đứng ngay trước nó. Hậu tố bắt đầu tại p có n-p tiền tố không rỗng; đúng LCP tiền tố đầu đã xuất hiện trong các hậu tố trước, còn các độ dài lớn hơn tạo nội dung mới. Vì vậy ta cộng n - SA[i] - LCP[i] cho mọi hạng i.
Ý tưởng: Mọi xâu con là tiền tố của một hậu tố. Khi các hậu tố được duyệt theo thứ tự từ điển, các hậu tố có cùng một tiền tố nằm liên tiếp, nên phần trùng với toàn bộ những hậu tố đã duyệt có độ dài đúng bằng LCP với hàng xóm trước. Do đó mỗi xâu con phân biệt được cộng đúng một lần.
Ý tưởng: Độ phức tạp là O(n log n) thời gian và O(n) bộ nhớ.