Use Manacher's algo for comprehensive list of palindroms and try to calc 2 arrays:
beg[i] - number of palindroms begins at position i,
end[i] - number of palindroms ends at position i.
after that ans = beg[i + 1] * end[i] for every i.

To calc arrays you can use either O(n) offline (+=cnt at beg -= cnt after end; then sum) or efficient data structures.

Edited by author 22.05.2017 20:40