Farmer John có thông điệp bí mật muốn giấu đàn bò; đó là xâu dài ít nhất 2 chỉ chứa A..Z.
Để mã hóa, FJ thực hiện chuỗi “thao tác”. Một thao tác trên $S$ trước hết rút ngắn xâu bằng cách xóa ký tự đầu hoặc cuối, rồi nối xâu gốc $S$ vào đầu hoặc cuối. Ví dụ, một thao tác trên ABCD có thể tạo ra bốn xâu:
BCDABCD ABCABCD ABCDABC ABCDBCD
Cho xâu mã hóa cuối cùng, hãy đếm số cách FJ có thể tạo ra nó bằng một hoặc nhiều thao tác liên tiếp trên một xâu gốc nào đó. Các thao tác được coi là khác nhau dù tạo cùng kết quả mã hóa. Ví dụ, có bốn cách khác nhau tạo AAA từ AA, tương ứng với bốn thao tác trên.
Dữ liệu vào
- Dòng $1$: xâu dài không quá 100.
Dữ liệu ra
- Dòng $1$: số cách khác nhau tạo xâu này bằng một hoặc nhiều thao tác liên tiếp trên xâu gốc nào đó dài ít nhất 2. Nếu không có cách nào, in số không.
Ví dụ
Dữ liệu vào 1
ABABA
Dữ liệu ra 1
6
Ghi chú
Các cách khác nhau tạo ABABA là:
- Bắt đầu với xâu:
ABA -> AB+ABA - Bắt đầu với xâu:
ABA -> ABA+BA - Bắt đầu với xâu:
AB -> AB+A -> AB+ABA - Bắt đầu với xâu:
AB -> AB+A -> ABA+BA - Bắt đầu với xâu:
BA -> A+BA -> AB+ABA - Bắt đầu với xâu:
BA -> A+BA -> ABA+BA
Tác giả bài toán: Brian Dean và Lewin Gan