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
hdhphat06dona: 2023-05-26 17:28:52

How does the answer go 15? Cannot imagine.

fuadul_hasan: 2022-09-25 23:50:57

finally I have learned palindromic tree and solve this one. it was more fun. :)

sirjan13: 2019-10-25 22:17:01

Manacher + Prefix sums :))

rks14: 2019-10-14 12:51:33

Weak test cases. O(n^3) passes.

sfialok98: 2017-06-27 13:50:47

Nice problem..
Learned Palindromic tree..

Gaurav Dahima: 2016-08-31 20:25:28

O(n*n) passes, try MSUBSTR (a bit harder) after this.

Piyush Kumar: 2016-07-05 14:22:19

O(n) solution can survive better constraints! :)

minhthai: 2016-04-05 16:25:36

if u find it difficult, read the problem again :)

[Mayank Pratap]: 2016-03-02 09:24:25

Simple Memoisation :)

sandy: 2016-02-26 08:28:58

nice problem to try out palindromic tree :)


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