Mật Khẩu Ba Lần · canuc80k4807 · Thuật toán Canuc80k

Tìm xâu khác rỗng dài nhất $P$ sao cho $P$ là tiền tố của $S$ , là hậu tố của $S$ , và còn xuất hiện tại ít nhất một vị trí bắt đầu khác hai vị trí ấy. Các lần xuất hiện được phép chồng lấn.

Input

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

Output

In $P$ . Nếu không tồn tại, in $J u s t$ $a$ $l e g e n d$ .

Constraints

$1 \leq ∣ S ∣ \leq 1 0^{6}$ .
$S$ chỉ gồm chữ cái thường $a, \dots, z$ .
Ba lần xuất hiện phải có ba vị trí bắt đầu phân biệt; chúng có thể chồng lấn.

Scoring

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

Example

Test 1

Input

aaaaa

Output

aaa

Giải thích: Xâu aaa xuất hiện tại các vị trí bắt đầu $1, 2, 3$ theo $1$ -based; các lần này chồng lấn nhưng vẫn là ba vị trí khác nhau.

Ý tưởng: Tính Z, đếm với mỗi L có bao nhiêu vị trí i thỏa Z[i]≥L, rồi duyệt border từ dài xuống.
Chứng minh đúng: Điều kiện Z[n-L]≥L xác nhận tiền tố dài L cũng là hậu tố. Tổng số vị trí có Z[i]≥L đếm các vị trí bắt đầu khác nhau, gồm đầu và cuối; nếu số này ít nhất 3 thì có thêm một lần xuất hiện, dù có thể chồng lấn. Duyệt L giảm dần trả ứng viên dài nhất.
Độ phức tạp: O(n) thời gian và O(n) bộ nhớ.
Mẫu công khai: Trong aaaaa, tiền tố aaa cũng là hậu tố và xuất hiện thêm từ ký tự thứ 2; không có ứng viên dài 4 xuất hiện ba lần.