🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📚 Mới ra mắt – Gói giải đề có lời giải chi tiết · chấm bài tự động · thầy hỗ trợ 1 – 1. Nếu còn phân vân về khóa học chính thức, các em và phụ huynh có thể tham khảo các gói giải đề dưới đây để trải nghiệm trước hệ thống làm bài, cách thầy phân tích – giải bài và sự hỗ trợ trực tiếp của thầy:

• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Hà Nội 2024 – 2026 – KHTN, ĐHSP · 5 đề · 21 bài · C++ và Python
• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Phổ thông Năng khiếu TP.HCM 2004 – 2026 – 22 đề · 84 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 TP.HCM 2008 – 2026 – cấp Thành phố · 17 đề · 48 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 Hà Nội 2005 – 2026 – cấp Thành phố · 17 đề · 69 bài · C++ và Python

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Tối thứ Bảy, thầy Sơn chèo ghe ra chợ nổi Cái Răng nghe một nhóm đờn ca tài tử biểu diễn ngay trên sông. Thầy ghi lại toàn bộ bản đờn thành một xâu ~S~ gồm ~N~ chữ cái Latin thường, mỗi chữ cái là một nốt nhạc (hò, xự, xang, xê, cống...) được mã hoá thành một chữ.

Nghệ nhân rất thích điệp khúc: một đoạn nhạc được đờn liền hai lần. Tuy nhiên lần đờn thứ hai thường được "luyến láy" thêm cho mùi, nên có thể khác lần đầu ở vài nốt. Cụ thể, một đoạn liên tiếp ~S[s..s+2p-1]~ (độ dài chẵn ~2p \ge 2~) được gọi là một điệp khúc nếu khi chia đôi thành nửa đầu ~X = S[s..s+p-1]~ và nửa sau ~Y = S[s+p..s+2p-1]~ thì số vị trí ~j~ ~(0 \le j < p)~ mà ~X_j \ne Y_j~ không vượt quá ~K~.

Thầy Sơn muốn tìm điệp khúc dài nhất trong bản ghi để đem về dạy học trò. Nếu có nhiều điệp khúc cùng độ dài lớn nhất, thầy chọn điệp khúc có vị trí bắt đầu ~s~ nhỏ nhất.

Hãy giúp thầy Sơn.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ ~(1 \le N \le 2 \times 10^5,~ ~0 \le K \le 3)~.
• Dòng thứ hai chứa xâu ~S~ gồm đúng ~N~ chữ cái Latin thường. Các vị trí trong ~S~ được đánh số từ ~1~ đến ~N~.

Kết quả

In ra hai số nguyên: độ dài ~2p~ của điệp khúc dài nhất và vị trí bắt đầu ~s~ nhỏ nhất của một điệp khúc có độ dài đó. Nếu bản ghi không có điệp khúc nào, in ra 0 0.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~N \le 300~.
• Subtask 2 (~30\%~ số điểm): ~N \le 5000~.
• Subtask 3 (~20\%~ số điểm): ~K = 0~.
• Subtask 4 (~30\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 5 giây (C++ là 1 giây).

Sample Input 1

11 1
bcaaabcabbc

Sample Output 1

8 4

Giải thích

Đoạn aabcabbc (bắt đầu ở vị trí ~4~) có nửa đầu aabc, nửa sau abbc, chỉ lệch nhau ~1~ nốt ~\le K = 1~ nên là điệp khúc độ dài ~8~. Hai đoạn độ dài ~10~ là bcaaabcabb (hai nửa bcaaa, bcabb lệch ~2~ nốt) và caaabcabbc (lệch ~3~ nốt) đều không phải điệp khúc.

Sample Input 2

10 0
baabcabcab

Sample Output 2

6 3

Giải thích

Với ~K = 0~, hai nửa phải giống hệt nhau. Các đoạn abcabc (vị trí ~3~), bcabca (vị trí ~4~), cabcab (vị trí ~5~) đều là điệp khúc độ dài ~6~; thầy Sơn chọn vị trí nhỏ nhất là ~3~. Không có điệp khúc nào dài hơn.

Nguồn: Đề tự luyện HSG Tin học quốc gia (đề tự soạn).