NUMOFPAL - Number of Palindromes

no tags 

Each palindrome can be always created from the other palindromes, if a single character is also a palindrome. For example, the string "malayalam" can be created by some ways:

  • malayalam = m + ala + y + ala + m
  • malayalam = m + a + l + aya + l + a + m

We want to take the value of function NumPal(s) which is the number of different palindromes that can be created using the string S by the above method. If the same palindrome occurs more than once then all of them should be counted separately.

Input

The string S.

Output

The value of function NumPal(s).

Limitations

0 < |s| <= 1000

Example

Input:
malayalam

Output:
15

hide comments
Sumit Vohra: 2016-01-18 19:59:43

0.0 manacher's rox

achiever202: 2013-07-09 08:27:37

will the initial string be a palindrome ??

Juɑƞ Chɑpɑrro: 2013-05-19 19:48:00

imput:
a
aa
aaa
aaaa
output:
1
3
6
10

Last edit: 2013-03-29 02:23:00
saket diwakar: 2013-01-28 21:48:07

simple one...:)

god_father: 2012-12-19 08:36:50

what should be output for string "aaa"?

David Gómez: 2012-04-06 14:13:59

@Mohamed Maher:
The answer are in the following format:
a b str where substr(s, a, b) = str

0 0 m
0 8 malayalam
1 1 a
1 3 ala
1 7 alayala
2 2 l
2 6 layal
3 3 a
3 5 aya
4 4 y
5 5 a
5 7 ala
6 6 l
7 7 a
8 8 m

lucky: 2012-04-06 14:13:59

can some provide some trickier test cases ??
Initial string will always be a palindrome??

Last edit: 2010-10-27 06:32:31
Mohamed Maher: 2012-04-06 14:13:59

can anyone write the 15 palindrome

Radhakrishnan Venkataramani: 2012-04-06 14:13:59

Dont think this s COUNTPAL problem of CODECHEF OCT 10 ..
this s a simpler version of that

sudipto das: 2012-04-06 14:13:59

@manmeet:read the problem carefully...it is not the problem u have assumed..(i had also thought so but later found out it is a different problem....)


Added by:The quick brown fox jumps over the lazy dog
Date:2010-10-18
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Udit Agarwal