Một xâu con được gọi là lặp nếu cùng nội dung của nó 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.
Hãy tìm một xâu con lặp có độ dài lớn nhất.
Input
Dòng duy nhất chứa xâu S.
Output
Nếu tồn tại xâu con lặp, in một xâu có độ dài lớn nhất. Khi có nhiều đáp án, có thể in bất kỳ đáp án nào.
Nếu không có xâu con lặp, in −1.
Constraints
1≤∣S∣≤105.
S chỉ gồm các chữ cái thường tiếng Anh từ a đến z.
Hai occurrence hợp lệ chỉ cần có vị trí bắt đầu khác nhau; chúng không bắt buộc phải rời nhau.
Scoring
Subtask 1 (50% số điểm): ∣S∣≤2000.
Subtask 2 (50% số điểm): Không có giới hạn bổ sung.
Example
Test 1
Input
banana
Output
ana
Giải thích: ana xuất hiện từ vị trí thứ 2 và 4 theo cách đánh số 1-based. Không có xâu con độ dài 4 nào xuất hiện hai lần, nên ana là đáp án tối ưu.
Lời giải tóm tắt
Ý tưởng: Dựng suffix array và mảng LCP. Nếu một xâu con xuất hiện ở hai vị trí, hai hậu tố tương ứng có tiền tố chung bằng xâu đó. Trong thứ tự suffix array, giá trị LCP lớn nhất giữa mọi cặp hậu tố luôn xuất hiện ở một cặp kề nhau; vì vậy chỉ cần lấy phần tử lớn nhất của mảng LCP và in tiền tố tương ứng.
Ý tưởng: Mỗi LCP kề tạo một xâu con lặp hợp lệ. Ngược lại, với hai hậu tố bất kỳ, LCP của chúng bằng giá trị nhỏ nhất trên đoạn LCP kề giữa hai hạng, nên một LCP kề trong đoạn không thể nhỏ hơn độ dài của xâu con chung đang xét. Hai chiều chứng minh giá trị lớn nhất của mảng LCP đúng bằng độ dài tối ưu.
Ý tưởng: Độ phức tạp là O(n log n) thời gian và O(n) bộ nhớ. Checker kiểm tra độ dài tối ưu và cho phép mọi nội dung hợp lệ, đúng với yêu cầu “in bất kỳ”.