#376. DISTICH - Câu đối Tết

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: Chưa có dữ liệu
Đưa lên bởi: Chùm CUỐI

Đề bài

Thời gian luộc bánh Chưng thường khá lâu, có thể đến 9-10 tiếng. Vì thời gian luộc bánh Chưng lâu như vậy nên trong thời gian này các bạn thường tìm các trò chơi để giết thời gian. Hạnh là một học sinh học rất giỏi Văn nên Hạnh lại tranh thủ sưu tầm câu đối cho ngày Tết (thay vì chơi các trò chơi khác). Và Hạnh đã tìm được một câu đối rất hay là một xâu ký tự s . Lúc này có rất nhiều bạn đến xin “copy” câu đối của Hạnh. Tuy nhiên, mỗi bạn sau khi “copy”, vì không muốn câu đối của mình giống hoàn toàn của bạn Hạnh và của những bạn khác đã “copy” trước đó nên đã chọn một đoạn các ký tự liên tiếp và thay bằng chính đoạn ký tự đó nhưng theo thứ tự ngược lại. Nam là một học sinh giỏi Toán nên Nam lại đặt ra câu hỏi: Từ câu đối của Hạnh, với cách thức “copy” như trên (chỉ “copy” từ câu đối của Hạnh, tránh sự “tam sao thất bản”), có thể tạo ra bao nhiêu câu đối khác nhau (bao gồm cả câu đối của Hạnh)?

Là một học sinh giỏi Tin, em hãy giúp Nam trả lời câu hỏi trên nhé.

Dữ liệu vào:

  • Một dòng duy nhất chứa câu đối của bạn Hạnh là một xâu ký tự s chỉ gồm các chữ cái la-tinh thường (‘a’, …., ‘z’).

Dữ liệu ra:

  • Một số nguyên dương duy nhất là số câu đối khác nhau có thể có.

Ví dụ:

Dữ liệu vào:
abab

Dữ liệu ra:

5
Giải thích:
  • có tất cả 5 câu đối khác nhau là “abab”, “baab”, “aabb”, “baba”, “abba” (đoạn chữ đậm chính là đoạn được đảo ngược).

Giới hạn:

Trong tất cả các test, độ dài xâu s không quá 10^5 . Trong đó:

  • Subtask \#1: 40\% số test ứng với 40\% số điểm có độ dài xâu s không quá 10^2 .
  • Subtask \#2: 20\% số test khác ứng với 20\% số điểm có độ dài xâu s không quá 10^3 .
  • Subtask \#3: 10\% số test khác ứng với 10\% số điểm có s chỉ chứa 2 ký tự ‘a’, ‘b’.
  • Subtask \#4: 30\% số test còn lại ứng với 30\% số điểm không có ràng buộc gì thêm.