Xâu con lặp
Xem PDF
Đ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
2
Test 2
Input
2
xy
Output
0
Test 3
Input
13
trangeorange
Output
5
Bình luận
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.