Đoạn Lặp Dài Nhất · canuc80k1913

Cho một xâu $s$ có độ dài $n$ . Một xâu con liên tiếp được gọi là lặp nếu cùng nội dung đó xuất hiện tại ít nhất hai vị trí bắt đầu khác nhau trong $s$ .

Hai lần xuất hiện được phép chồng lấn. Ví dụ, trong ababa, xâu aba xuất hiện từ vị trí $0$ và $2$ , nên vẫn được xem là lặp.

Hãy tìm độ dài lớn nhất của một xâu con lặp. Nếu không có xâu con không rỗng nào xuất hiện ít nhất hai lần, hãy in $0$ .

Input

Dòng đầu chứa số nguyên $n$ .
Dòng thứ hai chứa xâu $s$ dài đúng $n$ .

Output

In một số nguyên: độ dài lớn nhất của một xâu con xuất hiện ít nhất hai lần.

Constraints

$1 \leq n \leq 2 \cdot 1 0^{5}$ .
$s$ chỉ gồm chữ cái thường từ $a$ đến $z$ .

Scoring

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

Example

Test 1

Input

5
ababa

Output

Giải thích: Xâu aba dài $3$ xuất hiện từ vị trí $0$ và $2$ ; hai lần xuất hiện chồng lấn tại một ký tự nhưng vẫn hợp lệ. Không có xâu con dài $4$ nào xuất hiện hai lần.

Ý tưởng: Với một độ dài cố định L, xây hash tiền tố của s cho phép lấy dấu vân tay của mọi cửa sổ dài L trong O(1). Đưa các dấu vân tay vào một tập; nếu gặp giá trị đã có thì tồn tại hai lần xuất hiện, kể cả khi hai cửa sổ chồng lấn.
Ý tưởng: Tính chất kiểm tra là đơn điệu: nếu một xâu con dài L xuất hiện hai lần thì prefix dài L-1 của hai lần xuất hiện cũng bằng nhau. Vì vậy ta nhị phân độ dài lớn nhất trong [0,n-1] và dùng double hash trong mỗi lần kiểm tra.
Ý tưởng: Độ phức tạp: O(n log n) thời gian kỳ vọng và O(n) bộ nhớ.