NKNL2 - Chuỗi hạt (Hard version)
Giới hạn- Thời gian: 0.534s
- 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.
Đề bài tương tự bài "Chuỗi hạt" (NKNL) nhưng có giới hạn lớn hơn.
Như ta biết, một chuỗi hạt có thể được xâu từ rất nhiều hạt ngọc màu sắc khác nhau. Để tiện lợi, ta dùng các chữ cái in thường để mô tả các màu sắc: chẳng hạn chữ a mô tả màu đỏ, chữ b mô tả màu xanh, v.v.. Các hạt ngọc có thể có 26 màu khác nhau tương ứng với 26 chữ cái in thường. Như vậy, một chuỗi hạt có thể được biểu diễn bởi một xâu ký tự gồm các chữ cái in thường, mỗi ký tự mô tả màu của các hạt ngọc theo chiều kim đồng hồ bắt đầu từ một hạt ngọc nào đó.
Tuy nhiên, do chuỗi hạt có dạng vòng tròn, nên có thể có những chuỗi ký tự khác nhau cùng biểu diễn một chuỗi hạt, chẳng hạn bacade và cadeba có thể cùng biểu diễn chuỗi hạt. Để tránh tình trạng này, ta quy định trong các chuỗi ký tự cùng thể hiện một chuỗi hạt, ta chỉ sử dụng chuỗi ký tự có thứ tự từ điển nhỏ nhất để biểu diễn chuỗi hạt đó. Như vậy với chuỗi hạt ở ví dụ nêu trên chỉ biểu diễn bằng chuỗi acadeb.
Để đảm bảo tính thẩm mỹ, mỗi chuỗi hạt cần có ít nhất 5 hạt ngọc.
Yêu cầu: Cho một chuỗi ký tự S gồm các chữ cái in thường. Nhiệm vụ của bạn là đếm xem có bao nhiêu chuỗi con gồm các ký tự liên tiếp của S có thể biểu diễn một chuỗi hạt nào đó.
Input
Chuỗi ký tự S, gồm các chữ cái in thường (độ dài không quá 1000).
Output
Ghi ra một số nguyên duy nhất là số chuỗi con gồm các ký tự liên tiếp của S có thể biểu diễn một chuỗi hạt nào đó.
Example
Input: absdcabd Output: 1 Giải thích Chỉ duy nhất 1 chuỗi hạt là : absdc
- Người up: racer
- Nguồn bài: PTNK Team Selection 2008