Solución:
Estoy de acuerdo en que la lógica no es del todo correcta en la explicación del enlace. Les doy algunos detalles a continuación.
El algoritmo de Manacher llena una tabla P[i] que contiene qué tan lejos se extiende el palíndromo centrado en i. Si p[5]= 3, entonces tres caracteres a cada lado de la posición cinco son parte del palíndromo. El algoritmo aprovecha el hecho de que si ha encontrado un palíndromo largo, puede completar rápidamente los valores de P en el lado derecho del palíndromo observando los valores de P en el lado izquierdo, ya que en su mayoría deberían ser los mismo.
Comenzaré explicando el caso del que estaba hablando y luego expandiré esta respuesta según sea necesario.
R indica el índice del lado derecho del palíndromo centrado en C. Aquí está el estado en el lugar que indicó:
C=11
R=20
i=15
i'=7
P[i']=7
R-i=5
y la lógica es así:
if P[i']<=R-i: // not true
else: // P[i] is at least 5, but may be greater
El pseudocódigo en el enlace indica que P[i] debe ser mayor o igual que P[i’] si la prueba falla, pero creo que debería ser mayor o igual que Ri, y la explicación lo respalda.
Dado que P[i’] es mayor que Ri, el palíndromo centrado en i ‘se extiende más allá del palíndromo centrado en C. Sabemos que el palíndromo centrado en i tendrá al menos Ri caracteres de ancho, porque todavía tenemos simetría hasta ese punto, pero tenemos que buscar explícitamente Más allá de eso.
Si p[i’] no hubiera sido mayor que Ri, entonces el palíndromo más grande centrado en i ‘está dentro del palíndromo más grande centrado en C, por lo que habríamos sabido que P[i] no podría ser más grande que P[i’]. Si lo fuera, tendríamos una contradicción. Significaría que podríamos extender el palíndromo centrado en i más allá de P[i’], pero si pudiéramos, también podríamos extender el palíndromo centrado en i ‘debido a la simetría, pero ya se suponía que era lo más grande posible.
Este caso se ilustra previamente:
C=11
R=20
i=13
i'=9
P[i']=1
R-i=7
En este caso, P[i’]<= Ri. Dado que todavía estamos a 7 caracteres del borde del palíndromo centrado en C, sabemos que al menos 7 caracteres alrededor de i son los mismos que los 7 caracteres alrededor de i '. Como solo había un palíndromo de un carácter alrededor de i ', también hay un palíndromo de un carácter alrededor de i.
j_random_hacker notó que la lógica debería ser más así:
if P[i']<R-i then
P[i]=P[i']
else if P[i']>R-i then
P[i]=R-i
else P[i]=R-i + expansion
Si p[i’] Si p[i’] > Ri, entonces sabemos que P[i]== Ri, porque de lo contrario el palíndromo centrado en C se habría extendido más allá de R. Entonces, la expansión solo es realmente necesaria en el caso especial donde P[i’]== Ri, entonces no sabemos si el palíndromo en P[i] puede ser más largo. Esto se maneja en el código real configurando P[i]= min (P[i’], Ri) y luego siempre expandiéndose. Esta forma de hacerlo no aumenta la complejidad del tiempo, porque si no es necesaria ninguna expansión, el tiempo que se tarda en hacer la expansión es constante. He encontrado una de las mejores explicaciones hasta ahora en el siguiente enlace: http://tarokuriyama.com/projects/palindrome2.php También tiene una visualización para el mismo ejemplo de cadena (babcbabcbaccba) utilizado en el primer enlace mencionado en la pregunta. Aparte de este enlace, también encontré el código en http://algs4.cs.princeton.edu/53substring/Manacher.java.html Espero que sea útil para otros que se esfuerzan por comprender el meollo de este algoritmo. El algoritmo en este sitio parece comprensible hasta cierto punto http://www.akalin.cx/longest-palindrome-linear-time Para comprender este enfoque en particular, lo mejor es intentar resolver el problema en papel y captar los trucos que puede implementar para evitar buscar el palíndromo para cada centro posible. Primero responda usted mismo, cuando encuentre un palíndromo de una longitud determinada, digamos 5, ¿no puede, como siguiente paso, saltar al final de este palíndromo (omitiendo 4 letras y 4 letras intermedias)? Si intentas crear un palíndromo de longitud 8 y colocas otro palíndromo de longitud> 8, cuyo centro está en el lado derecho del primer palíndromo notarás algo gracioso. Pruébelo: Palíndromo con longitud 8 – WOWILIKEEKIL – Me gusta + ekiL = 8 Ahora, en la mayoría de los casos, podría escribir el lugar entre dos E como centro y el número 8 como longitud y saltar después de la última L para buscar el centro del palíndromo más grande. Este enfoque no es correcto, ya que el centro del palíndromo más grande puede estar dentro de ekiL y lo perderías si saltaras después de la última L. Después de encontrar LIKE + EKIL, coloque 8 en la matriz que usan estos algoritmos y esto se ve así: [0,1,0,3,0,1,0,1,0,3,0,1,0,1,0,1,8] por [#,W,#,O,#,W,#,I,#,L,#,I,#,K,#,E,#] El truco es que ya sabe que lo más probable es que los próximos 7 (8-1) números después del 8 sean los mismos que en el lado izquierdo, por lo que el siguiente paso es copiar automáticamente 7 números de la izquierda de 8 a la derecha de 8 manteniendo en tenga en cuenta que aún no son definitivos. La matriz se vería así [0,1,0,3,0,1,0,1,0,3,0,1,0,1,0,1,8,1,0,1,0,1,0,3] (estamos a las 8) por [#,W,#,O,#,W,#,I,#,L,#,I,#,K,#,E,#,E,#,K,#,I,#,L] Hagamos un ejemplo, que tal salto destruiría nuestra solución actual y veamos qué podemos notar. WOWILIKEEKIL: intentemos hacer un palíndromo más grande con el centro en algún lugar dentro de EKIL. Pero no es posible, tenemos que cambiar la palabra EKIL por algo que contenga palíndromo. ¿Qué? OOOOOh – ese es el truco. La única posibilidad de tener un palíndromo más grande con el centro en el lado derecho de nuestro palíndromo actual es que ya está en el lado derecho (e izquierdo) del palíndromo. Intentemos construir uno basado en WOWILIKEEKIL. Necesitaríamos cambiar EKIL a, por ejemplo, EKIK con I como centro del palíndromo más grande; recuerde cambiar LIKE a KIKE también. Las primeras letras de nuestro complicado palíndromo serán: WOWIKIKEEKIK como dije antes, deja que el último yo sea el centro del palíndromo más grande que KIKEEKIK: WOWIKIKEEKIKEEKIKIW Hagamos la matriz a nuestro antiguo pallindrom y descubramos cómo aprovechar la información adicional. por [_ W _ O _ W _ I _ K _ I _ K _ E _ E _ K _ I _ K _ E _ E _ K _ I _ K _ I _ W ] será we know that the next I – a 3rd will be the longest pallindrome, but let’s forget about it for a bit. lets copy the numbers in the array from the left of 8 to the right (8 numbers) [0,1,0,3,0,1,0,1,0,3,0,3,0,1,0,1,8,1,0,1,0,3,0,3] En nuestro bucle estamos entre E con el número 8. ¿Qué tiene de especial I (centro futuro del pallíndromo más grande) que no podemos saltar directamente a K (la última letra del pallíndromo más grande actualmente)? Lo especial es que supera el tamaño actual de la matriz … ¿cómo? Si mueve 3 espacios a la derecha de 3, está fuera de la matriz. Significa que puede estar en el medio del palíndromo más grande y lo más lejos que puedes saltar es esta letra I. Perdón por la longitud de esta respuesta, quería explicar el algoritmo y puedo asegurarles que @OmnipotentEntity tenía razón, lo entiendo aún mejor después de explicártelo 🙂
[0,1,0,3,0,1,0,1,0,3,0,3,0,1,0,1,8