Bài 4 (5,0 điểm)

Chuỗi lặp lại là chuỗi mà khi đọc từ trái sang phải có một đoạn ký tự liền sau giống hệt đoạn ký tự liền trước nó. Độ dài chuỗi lặp lại nhỏ nhất là 2 ký tự và luôn là một số chẵn. Ví dụ: chuỗi abab là chuỗi lặp lại; chuỗi abcab không phải chuỗi lặp lại.

Viết chương trình theo yêu cầu sau:

Input: cho trong tập tin BAI04.INP một chuỗi ký tự S có độ dài không quá 255 ký tự.

Output: ghi vào tập tin BAI04.OUT chuỗi con lặp lại dài nhất của S. Chuỗi con của S là một dãy ký tự liên tiếp trong S có độ dài không vượt quá độ dài của S. Nếu không tìm được chuỗi lặp lại, ghi KHONG TIM DUOC.

Ví dụ

BAI04.INP

zababcabcdq
  

BAI04.OUT

abcabc