Bậc đối xứng

HSG lớp 9 - Vĩnh Phúc 2012-2013 - Bài 2/3
 Xâu đối xứng là xâu đọc từ trái qua phải giống như đọc từ phải qua trái, chẳng hạn các xâu abba, madam là các xâu đối xứng. Người ta định nghĩa bậc đối xứng của xâu S, kí hiệu deg(S), như sau:
   Nếu S không phải là xâu đối xứng hoặc S có độ dài bằng 1 thì bậc đối xứng của S bằng 0 (viết là: deg(S)=0).
   Nếu xâu S là xâu đối xứng có độ dài lớn hơn 1, giả sử S=S1S2…SN (N > 1), thì bậc đối xứng của S được tính theo công thức: deg(S)= 1+ deg(T), trong đó xâu T là nửa trái của S theo nghĩa: T = S1S2…Sk với k = (N + 1) div 2.
Chẳng hạn:
   deg(x) = 0 vì x có độ dài bằng 1.
   deg(x0) = 0 vì x0 không đối xứng.
   deg(x0x) = 1 vì deg(xox) = 1 + deg(xo).
   deg(xoxxox) =2 vì deg(xoxxox)=1+deg(xox)
Cho xâu S độ dài không vượt quá 200 chỉ gồm các chữ cái latin thường, hãy xác định bậc  đối xứng của S.
Dữ liệu (PALINDEG.INP)
   Dòng 1: xâu S.
Kết quả (PALINDEG.OUT)
   Dòng 1: số nguyên là bậc đối xứng của xâu S.
Ví dụ
          PALINDEG.INP                 PALINDEG.OUT   
              Bobobbobob                                3 

                                                           Lời giải tham khảo