Xâu con lặp

Tác giả:

Dạng bài

Điểm: 300 (p) Thời gian: 2.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho xâu \(S\) độ dài \(N\), hãy lập trình xác định độ dài lớn nhất có thể của một xâu con xuất hiện từ hai lần trở lên trong \(S\) (hai lần xuất hiện này không được giao nhau). Nói cách khác, tìm số nguyên \(l\) lớn nhất sao cho tồn tại hai số chỉ số \(i_1\) và \(i_2\) thỏa mãn:

\(1\leq i_1, i_2\leq N-l+1\).
\(i_1+l\leq i_2\).
\(S[i_1+j]=S[i_2+j]\) với mọi \(j=0,1,2,...,l-1\).

Nếu không tồn tại số nguyên dương \(l\) thỏa mãn thì in ra \(0\).

Input

Dòng đầu chứa số nguyên dương \(N\) \((N\leq 5000)\).
Dòng tiếp theo chứa xâu \(S\) độ dài \(N\) chỉ gồm các chữ cái latin in thường.

Output

In ra độ dài lớn nhất tìm được.

Example

Test 1

Input

5
ababa

Output

Test 2

Input

2
xy

Output

Test 3

Input

13
trangeorange

Output

Bình luận

-2051

tkvinhtruongquang 8:59 a.m. 5 Tháng 9, 2021 ← đã chỉnh sửa →

hàm băm là gì vậy mn 🙂

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.