Contar palíndromos dobles en secuencia int dado

Question

Para un número de cheque dado secuencia int de palíndromos dobles, donde por doble palíndromo que secuencia media de dos mismos palíndromos sin descanso entre ellos. Así, por ejemplo:

en 1 0 1 1 0 1 1 0 tenemos 1 como un palíndromo que aparece 2 veces sin un descanso,

en 1 0 1 5 1 0 1 hemos 1 0 1 pero está separado

(aparte de los otros palíndromos en estas secuencias)

datos Problema ejemplo de ensayo es:

  

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

con respuestas

  

8 0 9

Manacher es obvia para la mendicidad, pero no estoy seguro de qué hacer a continuación. Cualquier idea apreciados. La complejidad debe ser inferior a 2 ^ n supongo.

EDIT: int aquí se trata como un solo elemento del alfabeto

Answer 1

Dado que ya conoce un algoritmo para encontrar todos los palíndromos (que por cierto es bastante impresionante), todo lo que hay que hacer es lo siguiente. Tenga en cuenta que un "doble palíndromo" también es un palíndromo:
revertir (PP) = inversa (P) inversa (P) = PP.

Así que entre todos los palíndromos (a,b) a encontrar (donde por (a,b) me refiero a un palíndromo de la posición a a la posición b), es necesario encontrar (i,j,k) tal que (i,j), (j,k) y (i,k) son todos los palíndromos, y j-i=k-j. De manera equivalente, para cada (i,j) palíndromo a encontrar, sólo tiene que k = 2j-i conjunto, y la comprobación de si tanto (k,j) y (i,k) son palíndromos.

Si los primeros retornos paso m palíndromos en total, esto lleva tiempo O (M) (suponiendo que almacenó ellos de tal manera que la comprobación de si existe un palíndromo es O (1)), de modo O (n ² ), en el peor de los casos. Creo que esto debe ser óptima en el peor de los casos (considere una cadena de todos los 1s).

Answer 2

Yo empezaría con 2 colecciones:

• una colección de 'creciente' secuencias
• una colección de 'contracción' secuencias

El algoritmo funciona de esta manera:

• Inicialmente ambas colecciones están vacíos
• Handle los valores del vector de una en una, suponemos que ahora estamos buscando a su valor V
• bucle sobre todos 'creciente' secuencias
  • Si el último valor de una secuencia creciente es igual a V, copiar la secuencia creciente a la colección de secuencias de contracción, remove V desde el extremo de la nueva secuencia encogimiento
  • Si el valor uno, pero en último lugar de la secuencia de crecimiento es igual a V, copia la secuencia creciente a la colección de la contracción de secuencias, quitar los 2 últimos elementos (V y el último) de la secuencia de encogimiento
• bucle sobre todos 'encogimiento' secuencias
  • Si el último valor de la secuencia de contracción es igual a V, elimina de la secuencia de contracción. Si una secuencia de reducción se vacía, hemos encontrado un palíndromo.
  • Si el último valor de la secuencia de la contracción no es igual a V, Suprimir esta secuencia de encogimiento
• Finalmente hacer una nueva secuencia creciente que consiste en solamente V

De hecho, las secuencias de crecimiento son secuencias que pueden volverse un palíndromo una vez, mientras que las secuencias reducidos son 'parcialmente' un palíndromo.