Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKNL2 - Chuỗi hạt (Hard version)

Đề 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


Được gửi lên bởi:Race with time
Ngày:2009-01-01
Thời gian chạy:0.178s-0.534s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:PTNK Team Selection 2008

hide comments
2012-10-06 04:36:36 Ðỗ Bá Hải
bài này quen quen
2011-07-28 17:13:10 trandatbav
Chứng tỏ ăn may rồi =))
2011-07-28 16:54:24 Noyethug
edit:đã AC

Last edit: 2011-12-21 11:55:37
2011-06-14 05:47:51 Noyethug
PS cho em hỏi em sai test nào ạ............:-/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.