Count double palindromes in given int sequence

Question

For a given int sequence check number of double palindromes, where by double palindrome we mean sequence of two same palindromes without break between them. So for example:

in 1 0 1 1 0 1 we have 1 0 1 as a palindrome which appears 2 times without a break,

in 1 0 1 5 1 0 1 we have 1 0 1 but it's separated

(apart from the other palindromes in these sequences)

Problem example test data is:

3

12 0 1 1 0 0 1 1 0 0 1 1 0

12 1 0 1 0 1 0 1 0 1 0 1 0

6 3 3 3 3 3 3

with answers

8 0 9

Manacher is obvious for the begging, but I'm not sure what to do next. Any ideas appreciated. Complexity should be below n^2 I guess.

EDIT: int is here treated as single element of alphabet

Answer 1

I would start with 2 collections:

• a collection of 'growing' sequences
• a collection of 'shrinking' sequences

The algorithm works like this:

• Initially both collections are empty
• Handle the values of the vector one by one, assume we are now looking at value V
• Loop over all 'growing' sequences
  • If the last value of a growing sequence is equal to V, copy the growing sequence to the collection of shrinking sequences, remove V from the end of the new shrinking sequence
  • If the one-but-last value of the growing sequence is equal to V, copy the growing sequence to the collection of shrinking sequences, remove the last 2 elements (V and the last one) from the shrinking sequence
• Loop over all 'shrinking' sequences
  • If the last value of the shrinking sequence is equal to V, remove it from the shrinking sequence. If a shrinking sequence becomes empty, we have found a palindrome.
  • If the last value of the shrinking sequence is not equal to V, delete this shrinking sequence
• Finally make a new growing sequence consisting of only V

In fact the growing sequences are sequences that might become a palindrome once, while the shrinking sequences are 'partially' a palindrome.

Answer 2

Since you already know an algorithm for finding all palindromes (which BTW is pretty awesome), all you need to do is the following. Note that a "double palindrome" is also a palindrome:
reverse(PP) = reverse(P)reverse(P) = PP.

So among all palindromes (a,b) you find (where by (a,b) I mean a palindrome from position a to position b), you need to find (i,j,k) such that (i,j), (j,k), and (i,k) are all palindromes, and j-i=k-j. Equivalently, for each palindrome (i,j) you find, you just need to set k = 2j-i, and check whether both (k,j) and (i,k) are palindromes.

If the first step returns M palindromes in all, this takes O(M) time (assuming you stored them such that checking whether a palindrome exists is O(1)), so O(n²) in the worst case. I believe this should be optimal in the worst case (consider a string of all 1s).