Mô tả
Khu kho thiết bị Samsung SDS tại Thành phố Hồ Chí Minh quản lý hàng nghìn thiết bị, mỗi chiếc được gắn một đoạn mã định danh viết liền không dấu, gồm toàn chữ cái thường và chữ số. Hệ thống ghi lại nhật ký quét mã trong ngày dưới dạng một chuỗi dài, ví dụ a1b2a1b3a1.
Bộ phận kiểm toán phát hiện rằng một số đoạn mã con có thể xuất hiện nhiều lần do lỗi quét trùng hoặc lỗi hệ thống cũ. Để làm sạch dữ liệu, bạn cần xác định chiều dài lớn nhất của một đoạn mã con xuất hiện ít nhất hai lần (ở hai vị trí khác nhau) trong chuỗi nhật ký. Các lần lặp không được chồng lấn nhau tại cùng một vị trí, nhưng có thể nối nhau hoặc nằm tách biệt.
Đầu vào
Một chuỗi s duy nhất, gồm các ký tự chữ cái thường (a–z) và chữ số (0–9), độ dài từ 1 đến 1000.
Đầu ra
Một số nguyên là chiều dài đoạn mã con dài nhất xuất hiện ít nhất hai lần. Nếu không có đoạn nào lặp lại, trả về 0.
Ràng buộc
- 1 ≤ |s| ≤ 1000.
- Mỗi ký tự thuộc tập chữ cái thường hoặc chữ số.
- Một đoạn mã con trùng lặp phải xuất phát từ hai chỉ số bắt đầu khác nhau.
Ví dụ
Ví dụ 1
- Đầu vào:
a1b2a1 - Đầu ra:
2 - Giải thích: Đoạn
a1xuất hiện ở vị trí 0 và vị trí 4, chiều dài 2 là lớn nhất. Đoạna1bkhông lặp lại, nên đáp án là 2.
Ví dụ 2
- Đầu vào:
abcabc - Đầu ra:
3 - Giải thích: Đoạn
abclặp lại trọn vẹn ở vị trí 0 và 3, không có đoạn nào dài hơn thỏa mãn.
Ví dụ 3
- Đầu vào:
x9z7 - Đầu ra:
0 - Giải thích: Mọi ký tự đều khác nhau, không tồn tại đoạn con nào lặp lại.