[SPOJ] PALDR

Suppose s is concatenation of even palindromes
Let p=min{i | s[0..i] is an even palindrome}
Then there is a concatenation using s[0..p]
Proof: let s[0..q] be the first even palindrome in a decomposition of s (q>p)
Since s[0..q] is a palindrome, s[0..p] = s[q..q-p] = an even palindrome
=> s[0..p] s[p+1..q-p-1] s[q-p..q] is also a decomposition of s[0..q] (QED)
Algorithm:
1. search for p
2. continue the process with the string s[p+1 .. n-1]
The number of times we test for palindrome is O(n)
However, the complexity of each palindrome test could not be all O(n) and thus, the total complexity could not reach O(n^2)