NUMOFPAL  Number of Palindromes
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:
20230526 17:28:52
How does the answer go 15? Cannot imagine. 

fuadul_hasan:
20220925 23:50:57
finally I have learned palindromic tree and solve this one. it was more fun. :) 

sirjan13:
20191025 22:17:01
Manacher + Prefix sums :)) 

rks14:
20191014 12:51:33
Weak test cases. O(n^3) passes. 

sfialok98:
20170627 13:50:47
Nice problem..


Gaurav Dahima:
20160831 20:25:28
O(n*n) passes, try MSUBSTR (a bit harder) after this. 

Piyush Kumar:
20160705 14:22:19
O(n) solution can survive better constraints! :) 

minhthai:
20160405 16:25:36
if u find it difficult, read the problem again :) 

[Mayank Pratap]:
20160302 09:24:25
Simple Memoisation :) 

sandy:
20160226 08:28:58
nice problem to try out palindromic tree :) 
Added by:  The quick brown fox jumps over the lazy dog 
Date:  20101018 
Time limit:  0.100s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Udit Agarwal 