Number of even palindromes by concatenating two strings
<p>This problem popped into my mind.</p>

<p>I have two strings <code>s1</code> and <code>s2</code>, each with say, a maximum length of about 500 characters. How many sub-sequences of <code>s1+s2</code> (concatenation of <code>s1</code> and <code>s2</code>) are even palindromes, with the first half of the palindrome being a sub-sequence of <code>s1</code> and the second half being a sub-sequence of <code>s2</code>?</p>

<p>Of course the brute-force solution would be to find the number of pairs of sub-sequences of s1 and s2 where one is the reverse of the other. But with a length of about 500, this is too time consuming.</p>

<p>Any ideas?</p>