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.|

QBPAL - Đếm chuỗi đối xứng

Trong một buổi học viết chữ, Bờm phát hiện trong một số từ khi bỏ đi một số ký tự thì đọc ngược hay đọc xuôi đều giống nhau.

Ví dụ từ IOICAMP, khi xóa đi các chữ cái C,A,M,P, thì còn lại IOI là một từ đối xứng.

Bờm cảm thấy thú vị, và cậu tiếp tục thử xóa các ký tự khác, kết quả là có thêm nhiều từ đối xứng nữa: II, I, O, C… Nhưng nếu với một từ dài, cứ thử từng cách xóa như vậy thì thật mất thời gian. Bạn hãy viết chương trình giúp Bờm tính số cách xóa sao cho từ thu được đối xứng. Hai cách xóa chỉ khác nhau bởi thứ tự xóa các ký tự thì coi như trùng nhau.

Input

Một dòng duy nhất là từ cần tính số cách xóa, từ này chỉ chứa các chữ cái in hoa A, B, .., Z. ( Độ dài từ không quá 120 )

Output

Một số duy nhất là số cách xóa.

Example

Input:
IOICAMP

Output:
9

Được gửi lên bởi:special_one
Ngày:2008-10-11
Thời gian chạy:0.163s
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:Hứa Lê Thanh Vy

hide comments
2019-05-18 03:41:05
Bài toán thực chất là đếm số xâu con Palindrome. Gọi F[i, j] là số xâu con Palindrome trong xâu
S[i..j]. Nếu S[i] = S[j] thì F[i, j] = F[i + 1, j] + F[i, j - 1] + 1, nếu không thì F[i, j] = F[i + 1, j] + F[i, j - 1]
– F[i + 1, j - 1]. Lưu ý do kết quả rất lớn nên phải cài phép cộng và trừ của BigNum.
2018-12-11 07:11:19
QHD
2018-04-02 03:00:37
One Punch Man nhập =)) 1 đấm
Đức Thắng Lào Cai vô đối!!
2018-04-02 02:59:17
QHD 1 đấm AC =)))
Lào Cai vô đối !!!
2017-11-28 13:57:08
Thuat toan va code : http://123link.co/w1x7qUs
2017-11-06 04:39:31
nhật hào sạch
2015-10-11 16:13:42 The Legendary Tiger (NDHD)
Lời giải tham khảo: https://copcode.wordpress.com/2015/10/06/qbpal-spoj-dem-chuoi-doi-xung/
2015-09-16 16:20:47
THAM KHẢO TẠI https://traitaodo.wordpress.com/2015/09/16/dem-chuoi-doi-xung-qbpal/
2015-05-03 16:35:19 to_yeu_mao_hieu_dong
vất vả với cài số lớn
2014-11-15 05:47:07 never give up !!
không xóa kí tự nào vẫn tính là 1 cách nhá :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.