DTCSTR - Chuỗi mắc xích
Giới hạn- Thời gian: 1.64s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Sắp có một biểu đình đả đảo những đề bài do pirate viết ra. Lý do đơn giản là vì chúng quá dài và quá sến. pirate rất buồn khi nghe được điều đó. Nếu bắt anh ta thay đổi thì chẳng khác nào giết chết tâm hồn thi ca trong một con người. Nhưng vì tình yêu với mọi người, pirate quyết định đây là đề bài dài và sến cuối cùng mà anh sẽ viết ra.
Một ngày nọ, đang nghiên cứu môn stringology, anh chàng nổi hứng chuyển sang nghiên cứu môn philosophy (để chuẩn bị cho những năm tháng sẽ bị nó hành hạ sau này). Sau một ngày hì hục bên bên chồng sách về "Tư tưởng Hồ Chí Minh" và "Chủ nghĩa xã hội khoa học", anh ngẫm ra chân lý của cuộc sống : Mọi sự vật hiện hữu ở hiện tại đều do một sự vật hiện hữu ở quá khứ tạo thành, giống như những mắc xích của sự tiến hóa. Ngay lập tức, pirate áp dụng nó vào các chuỗi.
Vấn đề đặt ra là cho một chuỗi S, bạn hãy xác định độ dài của chuỗi A thỏa hai điều kiện sau:
- Chuỗi S phải phân tích được ra thành nhiều mắc xích. Mỗi mắc xích do một dãy các ký tự liên tiếp của S tạo thành và là một chuỗi A. Mỗi ký tự của chuỗi S phải thuộc vào ít nhất một mắc xích. Ví dụ: S = ababa được tạo thành từ mắc xích là ab a và a ba (khi ghép hai chuỗi này và để phần in đậm trùng lên nhau thì được chuỗi S).
- Độ dài chuỗi A phải là nhỏ nhất.
Input
Dữ liệu vào gồm các ký tự in thường viết liên tiếp nhau tạo thành chuỗi S (độ dài không quá 500000).
Output
Dữ liệu ra gồm một dòng duy nhất là độ dài của chuỗi A cần tìm.
Example
Input: abbaabbaa Output: 5
- Người up: khanhptnk
- Nguồn bài: Sưu tầm