Chu Kỳ Nhỏ Nhất Thông Báo Ga Sài Gòn

Mô tả

Tại ga Sài Gòn, một màn hình LED lớn hiển thị chuỗi thông báo giờ tàu chạy. Vì bộ nhớ của màn hình có hạn, ban quản lý ga muốn tối ưu hóa cách lưu trữ. Nhận thấy thông báo thường lặp đi lặp lại theo một đoạn mẫu cố định, họ quyết định chỉ lưu đoạn mẫu nhỏ nhất và dùng nó để tái tạo toàn bộ chuỗi.

Ví dụ, chuỗi thông báo hiện tại là 123123 thì đoạn mẫu cần lưu chỉ là 123, vì lặp 123 đúng hai lần sẽ ra chuỗi ban đầu.

Nhiệm vụ của bạn là: cho một chuỗi thông báo, hãy tìm và trả về đoạn mẫu ngắn nhất sao cho khi lặp lại đoạn mẫu đó một số nguyên lần (ít nhất một lần) thì sẽ thu được đúng chuỗi thông báo ban đầu.

Đầu vào

Một chuỗi s gồm các ký tự chữ cái và chữ số.

Đầu ra

Trả về một chuỗi là đoạn mẫu ngắn nhất có thể lặp lại để tạo thành chuỗi s.

Ràng buộc

• Độ dài chuỗi s nằm trong khoảng từ 1 đến 1000 ký tự.
• Chuỗi s chỉ chứa các ký tự chữ cái (a-z, A-Z) và chữ số (0-9).

Ví dụ

Ví dụ 1

• Đầu vào: "123123"
• Đầu ra: "123"
• Giải thích: Chuỗi 123 lặp lại 2 lần tạo thành 123123. Không có chuỗi con ngắn hơn có thể làm được điều tương tự.

Ví dụ 2

• Đầu vào: "ABABABAB"
• Đầu ra: "AB"
• Giải thích: Chuỗi AB lặp lại 4 lần tạo thành ABABABAB. Chuỗi ABAB cũng tạo được chuỗi gốc nhưng không phải là ngắn nhất.

Ví dụ 3

• Đầu vào: "XYZ"
• Đầu ra: "XYZ"
• Giải thích: Không thể chia XYZ thành các đoạn nhỏ hơn giống nhau, nên đoạn mẫu chính là chuỗi ban đầu.