Depois de passar cerca de 6-8 horas tentando digerir o algoritmo do Manacher, estou pronto para jogar a toalha. Mas antes que eu faça, aqui está um último tiro no escuro: alguém pode explicar isso? Eu não me importo com o código. Eu quero alguém para explicar oALGORITMO.

Aqui parece ser um lugar que os outros pareciam gostar de explicar o algoritmo:http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

Eu entendo porque você iria querer transformar a string, digamos, 'abba' em # a # b # b # a # Depois do que eu estou perdido. Por exemplo, o autor do site mencionado anteriormente diz que a parte principal do algoritmo é:

<code>                      if P[ i' ] ≤ R – i,
                      then P[ i ] ← P[ i' ]
                      else P[ i ] ≥ P[ i' ]. (Which we have to expand past 
                      the right edge (R) to find P[ i ])
</code>

Isso parece errado, porque ele diz em um ponto que P [i] é igual a 5 quando P [i '] = 7 e P [i] não é menor ou igual a R - i.

Se você não está familiarizado com o algoritmo, aqui estão mais alguns links:http://tristan-interview.blogspot.com/2011/11/longest-palindrome-substring-manachers.html (Eu tentei este, mas a terminologia é horrível e confusa. Primeiro, algumas coisas não estão definidas. Além disso, muitas variáveis. Você precisa de uma lista de verificação para lembrar qual variável está se referindo a quê.)

Outra é:http://www.akalin.cx/longest-palindrome-linear-time (boa sorte)

A essência básica do algoritmo é encontrar o palíndromo mais longo em tempo linear. Isso pode ser feito em O (n ^ 2) com uma quantidade mínima a média de esforço. Este algoritmo é suposto ser "inteligente" para descer para O (n).