Number of pairs of strings such that their concatenation is a palindrome

Revision en4, by Not-Afraid, 2020-05-03 14:10:04

Given $$$N$$$ strings, we need to count how many pairs $$$1$$$ <= $$$i$$$, $$$j$$$ <= $$$N$$$ exists such that s[i] + s[j] is a Palindrome. Can anyone suggest an efficient approach for solving this problem?
1 <= $$$N$$$ <= 2000
1 <= |si| <= 1000

The lengths of all strings are not necessarily same and all the strings may not be unique.

My approach is to precompute hashes of the given strings and iterate over all pairs i, j now we want to concatenate the two strings $$$s[i] + s[j]$$$. For simplicity let's say $$$length(s[i]) <= length(s[j])$$$

1) if $$$length(s[i]) == length(s[j])$$$ then $$$hash(s[i])$$$ should be equal to $$$hash(reverse(s[j]))$$$.

2) otherwise take suffix of $$$s[j]$$$ of length equal to $$$s[i]$$$ and check if it's reverse is equal to $$$s[i]$$$ and also remaining prefix of $$$s[j]$$$ excluding the previous suffix should be palindrome.

Any approach other than hashing?

Tags #palindrome, rolling hashes

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English Not-Afraid 2020-05-03 14:11:34 62 (published)
en4 English Not-Afraid 2020-05-03 14:10:04 26
en3 English Not-Afraid 2020-05-03 14:08:40 132
en2 English Not-Afraid 2020-05-03 14:04:10 382
en1 English Not-Afraid 2020-05-03 13:59:19 463 Initial revision (saved to drafts)