Count double palindromes in given int sequence

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

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).

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.