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
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 :) 

Sumit Vohra:
20160118 19:59:43
0.0 manacher's rox


vinayawsm:
20140323 11:49:06
Last edit: 20161003 22:37:01 
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 