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

Правка en5, от Not-Afraid, 2020-05-03 14:11:34

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 or any link if it's solution is already published somewhere?

Теги #palindrome, rolling hashes

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский Not-Afraid 2020-05-03 14:11:34 62 (published)
en4 Английский Not-Afraid 2020-05-03 14:10:04 26
en3 Английский Not-Afraid 2020-05-03 14:08:40 132
en2 Английский Not-Afraid 2020-05-03 14:04:10 382
en1 Английский Not-Afraid 2020-05-03 13:59:19 463 Initial revision (saved to drafts)