DP,STRINGS, STRINGS SUFFIX STRUCTURES
In this problem, we need to find the number of ways to split a string S to substrings such that if there are k substrings (p1, p2, p3, …, pk) in partition, then pi = pk-i+1 for all i (1 ≤ i ≤ k) and k is even.
Let n be the length of the string s. Consider the string t = ss[n - 1]ss[n - 2]ss[n - 3]…s[n / 2 - 1]s[n / 2]. The problem can be reduced to finding the number of ways to partition string t into palindromic substrings of even length.
Proof: Let k be the total number of partitions. Let pi = pk - i + 1 = x1x2x3…xm where m denotes length of pi and xj denotes jth character of pi. The part of string t corresponding to these two partitions is x1xmx2xm - 1…xm - 1x2xmx1 which is an even length palindrome. Similarly, the converse is also true.
Dynamic programming can be used to solve the problem. Let dp* be the number of ways to partition t[1…i] into even length palindromes. Then, where t[j + 1…i] is an even length palindrome. Of course for odd i, dp* = 0.
Author’s solution can be found here