Tần Suất Lớn Nhất Theo Độ Dài · canuc80k6216

Cho một xâu chữ thường $S$ độ dài $n$ . Với mỗi độ dài $L$ từ $1$ đến $n$ , xét tất cả các xâu con liên tiếp của $S$ có đúng $L$ ký tự. Hãy tìm số lần xuất hiện lớn nhất của một xâu con như vậy.

Hai lần xuất hiện được tính riêng theo vị trí bắt đầu và được phép chồng lấn.

Input

Một dòng chứa xâu $S$ .

Output

In $n$ dòng. Dòng thứ $L$ chứa số lần xuất hiện lớn nhất của một xâu con độ dài $L$ .

Constraints

$1 \leq n \leq 2.5 \cdot 1 0^{5}$ .
$S$ chỉ gồm các chữ cái thường $a, \dots, z$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $n \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: Với độ dài $1$ , ký tự a xuất hiện $3$ lần. Với độ dài $2$ và $3$ , các xâu ab và aba lần lượt xuất hiện $2$ lần; mọi xâu con dài $4$ hoặc $5$ chỉ xuất hiện một lần.

Ý tưởng: Dựng suffix automaton của S. Mỗi lần thêm một ký tự, trạng thái cuối mới nhận occ = 1; clone nhận occ = 0. Sau khi dựng xong, xử lý trạng thái theo độ dài giảm dần và cộng occ[v] vào suffix link của v. Khi đó occ[v] là số vị trí kết thúc của mọi xâu thuộc trạng thái v.
Ý tưởng: Ghi occ[v] vào đáp án ở độ dài lớn nhất len[v]. Một trạng thái còn đại diện các độ dài ngắn hơn, vì vậy quét L giảm dần và thay ans[L] bằng max(ans[L], ans[L+1]). Đây chính là bước lấp toàn bộ khoảng độ dài.
Ý tưởng: Độ phức tạp O(n·alphabet) thời gian và O(n·alphabet) bộ nhớ với bảng 26 ký tự.