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

Правка en2, от Not-Afraid, 2020-05-03 14:04:10

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.

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(s[j]).
2) take suffix of s[j] of length equal to s[i] and check if they are equal and also remaining prefix of s[j] excluding the previous suffix should be palindrome.

Теги #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)