Tích Độ Dài Và Tần Suất Xâu Con Lớn Nhất

Buổi 56 — Suffix Array & LCP Data-structures
Points
60
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
string
Submissions
Đề bài

Cho một văn bản $S$ có độ dài $N$ chỉ gồm các chữ cái tiếng Anh in thường. Với mỗi xâu con liên tiếp khác rỗng $T$ của $S$, gọi $\text{occ}(T)$ là số lần $T$ xuất hiện trong $S$ (các lần xuất hiện có thể chồng lên nhau). Giá trị tầm quan trọng của xâu con $T$ được định nghĩa là $|T| \times \text{occ}(T)$, trong đó $|T|$ là độ dài của $T$. Hãy tìm giá trị $|T| \times \text{occ}(T)$ lớn nhất có thể trên mọi xâu con $T$ của $S$.

Dữ liệu vào

Một dòng duy nhất chứa xâu $S$ ($1 \le |S| \le 2 \cdot 10^5$) chỉ gồm các chữ cái in thường từ 'a' đến 'z'.

Dữ liệu ra

In ra một số nguyên duy nhất là giá trị lớn nhất của $|T| \times \text{occ}(T)$.

Ví dụ
Input Output
ababa 6
Giới hạn

Thời gian: 1.0s, Bộ nhớ: 256MB.

Draft saved