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

Revision en1, by Not-Afraid, 2020-05-03 13:59:19

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

My approach is to precompute hashes of the given strings. Now iterate over all pairs i, j now we want to concatenate the two strings s[i] + s[j].

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)