Hi guys,
I encountered a problem requiring us to find how many "Double Palindromes" are in the given input String.
A "Double Palindrome" is a string of concatenation of two palindromes with the same size. For example, "aabb", "aaaa" are the "Double Palindromes", but "abba" or "aaaabb" are not. Given an input string, the task is to calculate how many "Double Palindromes" exist in it. On the other word, our task is to calculate how many distinct pairs (l, r) satisfy the condition that S(l)S(l+1)...S(r) is "Double Palindromes".
Sample Input : "abacac" then output will be 6 because of : "ab", "ba", "ac", "ca", "ac" and "abacac" are "Double Palindromes".
Sorry for the missing: n <= 500000
constraints ??
sorry, i missed it. N <= 500000 with N is the size of given input string
n^2 is easy, brute force the left segment, and then with hashes check if it is a palindrome and the corresponding segment to the right (same # of symbols) is a palindrome, too. its just off the top of my head
to solve faster we can probably use Manaker to find for each index the longest palindrome with such center in O(n). And then somehow using these values quickly get the answer
for each center we have many ways to calculate P[i] = r with r is the radius satisfying r is max, and i — P[i] -> i + P[i] is a palindrome. But, i'm still stuck in how to calculate the answer
Kinda like this: for simplicity only find # where both palindromes are of odd length.
then we need # of pairs (i < j, for which j — i % 2 = 0) for which the values from manaker are >= (j — i) / 2, so the largest palindromes from centers i and j are able to "touch" together and thus form a double palindrome.
now the task is calculate # of such elements. if we take separately odd and even indices (make 2 half arrays), now the task becomes for each of these arrays find # of pairs of elements (i < j), for which a[i] and a[j] are both >= (j — i). to do this, iterate through i, now we get a segment of good potential j indices, where j > i, and a[i] >= j — i. for example it is [l, r]. now just add to the answer the number of elements a[j] on [l, r], which are > j — i <=> a[j] — j > -i. this can be done taking another array of a[j] — j, and just quering with segment tree number of elements bigger than -i. which should pass.
the first thing I came up with. this is of course an ugly solution, but seems doable this way. maybe can be done so much easier idk
Auto comment: topic has been updated by MathK30 (previous revision, new revision, compare).