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?
I think this algo works: Let's bruteforce i-th string, and suppose that len(j) <= len(i).In this case i + j is palindrome, if j — prefix of i, and suffix of i with lenght (len(i) — len(j)) — palindrome.So, we will bruteforce prefix of i and count amount of strings, that equal to our prefix.And we will add that value to answer, if the rest of string i is a palindrome.The first part can be done by using trie, and the second by using hashes.Don't forget to reverse i and do the same for reversed string i.This algo takes O(sum(len(i))) time.
The author says he doesn't want hashes....
Suppose,
$$$Suff(i)$$$ is the list of lengths of suffixes of $$$S_i$$$ which are palindrome
$$$Suff(i)$$$ can be computed efficiently using Manacher's algorithm.
Now create an Aho Corasick automaton using reverse strings of all the given strings. Now for each index $$$i$$$, check if there is an index $$$j$$$ such that $$$i \neq j$$$ and the reverse string of $$$S_j$$$ is a prefix of $$$S_i$$$. Aho Corasick automaton allows you to find all such indexes efficiently. If you find such an index $$$j$$$, then all you have left to do is to check if the remaining part of $$$S_i$$$ (that is the suffix of length $$$|S_i|-|S_j|$$$ of $$$S_i$$$) is a palindrome or not, which can be easily done using $$$Suff(i)$$$. This way you can find all valid pairs and count them.
UPD: My calculation was wrong. This won't pass the time limit.
This might help https://www.codechef.com/problems/PP