Biên Và Số Lần Xuất Hiện · canuc80k4812

Xét mọi tiền tố không rỗng của xâu $S$ đồng thời là hậu tố của $S$ ; toàn bộ xâu cũng được tính. Với mỗi độ dài hợp lệ $L$ , hãy đếm số vị trí bắt đầu mà tiền tố dài $L$ xuất hiện như một substring của $S$ . Các lần xuất hiện chồng lấn vẫn được tính.

Input

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

Output

Dòng đầu in số cặp $k$ . Mỗi dòng tiếp theo in $L$ $C$ , trong đó $C$ là số lần tiền tố dài $L$ xuất hiện. Các cặp được in theo $L$ tăng dần.

Constraints

$1 \leq ∣ S ∣ \leq 1 0^{5}$ .
$S$ chỉ gồm chữ cái hoa tiếng Anh.

Scoring

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

Example

Test 1

Input

ABACABA

Output

Giải thích: Các độ dài vừa là tiền tố vừa là hậu tố là $1, 3, 7$ ; chúng xuất hiện lần lượt $4, 2, 1$ lần.

Ý tưởng: Đếm tần suất các giá trị Z vào cnt, rồi cộng dồn từ phải sang trái để cnt[L] bằng số vị trí i thỏa Z[i]≥L. Duyệt L tăng dần; chỉ giữ những L mà tiền tố dài L đồng thời là hậu tố của S, và in cnt[L]. Toàn bộ xâu, tức L=n, luôn được tính.
Chứng minh đúng: Một vị trí bắt đầu i tạo ra một lần xuất hiện của tiền tố dài L đúng khi Z[i]≥L. Vì vậy tổng hậu tố của bảng tần suất Z cho đúng số lần xuất hiện của từng độ dài L. Điều kiện L=n hoặc Z[n-L]≥L chọn đúng và đủ các tiền tố cũng là hậu tố. Do đó mọi cặp được in đều chính xác và không bỏ sót độ dài hợp lệ nào.
Độ phức tạp: O(n) thời gian và O(n) bộ nhớ.
Mẫu công khai: Các độ dài biên là 1,3,7; số vị trí xuất hiện tương ứng là 4,2,1.