I think hashing might be a better option. Calculate forward and reverse hashes of each, then for each string, you can count how many hashes of reversed string are there.

Notice that every palindrome (..and each string in general..) can be written by repeating some pattern. For example, "aaa" = "a" * 3, "abab" = "ab" * 2 and "aba" = "aba" * 1. We can observe that two palindromes produce a new palindrome when connected to each other, only if their repeating pattern is the same (so "aa" and "a" works, but "aa" and "aba" doesn't). To find the smallest repeating pattern KMP (or in my case the Z-Algorithm) can be used.