¿Cómo elegir el próximo centro en el algoritmo palíndromo más largo?

Question

Esta es una pregunta acerca de la más larga palíndromo algoritmo discutido aquí hace algún tiempo. El blog citado , lo que explica el algoritmo, dice: "para recoger el próximo centro, tome el centro de los más largos sufijo apropiado capicúa del palíndromo actual" . Por desgracia, no proporcionan una prueba y yo no entiendo muy bien ¿Por qué el próximo centro es el centro de los más largos sufijo apropiado capicúa del palíndromo actual .

¿Alguien puede probar / explicarlo?

Answer 1

Así que nos estamos moviendo hacia la derecha ...

Diga su palíndromo "actual" es de 40 letras grandes. (Tal vez centrado en la posición 100. digamos) Usted está tratando de encontrar uno más grande.

(OK, puede haber una más grande que se encuentra a 900 letras de largo, y que es de 50.000 cartas a la derecha -... No involucrado totalmente con éste Eso está bien, pero vamos a llegar a que en el futuro Por ahora , tenemos que mover el centro a la derecha, mientras que en busca de palíndromos más largos de lo-40. Tiene sentido?)

Así que tenemos que mover hacia la derecha - podríamos dar un paso. Pero queremos avanzar en la medida de lo posible y sin perder ninguna.

Ahora bien, si los próximos uno a la derecha se va a incluir éste ... de hecho, tiene que incluir más a la derecha carta de este grupo de 40. (no puede ser más hacia la izquierda, como ya hemos comprobado, por lo que, se debe centrar después de 100, y, debido a que va a ser durante más de 40 , que debe son nuestra carta de la derecha , # 120).

Así que tan atrás tenemos que ir?

Bueno, no se puede volver atrás (de 120) más allá de un palíndromo ! Si no es un palíndromo en el medio que nunca será un palíndromo.

3333333333333331110111

Sólo se puede "volver" al 0. del 1 sentado a la izquierda del 0 (por ejemplo), nunca podría ser un palíndromo.

Así que es así de simple. tiene que incluir nuestra carta más a la derecha (si es que vamos a incluir cualquiera de nosotros en absoluto), y, ya quiero que sea lo más grande posible, y tiene que ser un palíndromo porque palíndromos sólo pueden iniciar (me refiero a "del medio") con palíndromos .

En el ejemplo anterior, no es posible que la 1 a la izquierda oa la 0, o digamos más a la derecha 3, podría nunca en este centro universo un palíndromo, no importa lo que más adelante encontrará a la derecha. No tienen palíndromos alrededor de ellos, para que pudieran "no ser" un centro palíndromo!

Tenga en cuenta que el 3 en el medio de los 3s podría posiblemente centrar un palíndromo más grande .... y no hay que olvidar que ya hemos comprobado esto es el palíndromo más largo hasta ahora (basado en centros, desde la izquierda), de manera que no puede ser verdad.

Así que cualquier palíndromo que es más largo que éste - más bien, el siguiente punto de partida posible para un palíndromo más largo que éste -. Es que 0

En otras palabras, es simplemente el centro del mayor palíndromo que actualmente tiene a la derecha. (Así, no el "111", que es un palíndromo pero corto, pero el "1110111", que es el más largo palíndromo se puede ver pegado a la derecha.)

De hecho, las dos posibilidades que tenemos para comprobar son (A) el "0" y (B) el "1" en el penúltimo punto. por supuesto, entre estos dos possibilties, tenemos que ir de izquierda a derecha, por lo que (A) el "0" es de hecho el siguiente para comprobar.

No se olvide de los dos (el 0 y el 1 en cuestión) son lo mismo que decir "hay un palíndromo 1110111 atascado hasta el final, y hay un palíndromo más corto 111 atascado hasta el final".

Por supuesto 1.110.111 es más largo, por lo que el centro de 1,110,111 obviamente a la izquierda del centro del 111.

El palíndromo más largo pegado a la derecha, por supuesto, tiene el centro más cercano a la izquierda.

Así que espero que deja claro sólo la parte específica de la discusión en el blog relacionado, el cual, se le preguntará sobre !!! Deliberadamente yo repetí en un número de maneras, es de esperar que ayude. Es el día de algoritmos de Jung:)

Una vez más por favor, tenga en cuenta que estoy en concreto y sólo tratando de aclarar la cuestión muy específica Michael preguntó sobre.

Bloody confundir eh?

Por cierto, yo simplemente ignorado el tema de caracteres en centros de fuera de carácter -. Pero es irrelevante para la comprensión de lo que preguntaste