Nachdem ich ungefähr 6-8 Stunden damit verbracht habe, den Algorithmus des Manachers zu verdauen, bin ich bereit, das Handtuch zu werfen. Aber bevor ich es tue, ist hier eine letzte Einstellung im Dunkeln: Kann es jemand erklären? Der Code interessiert mich nicht. Ich möchte, dass jemand das erklärtALGORITHMUS.

Hier scheint ein Ort zu sein, an dem andere den Algorithmus gerne erklärten:http://www.leetcode.com/2011/11/längste-palindromic-substring-part-ii.html

Ich verstehe, warum Sie die Zeichenfolge transformieren möchten, sagen Sie 'abba' zu # a # b # b # a # After, als ich verloren bin. Beispielsweise sagt der Autor der zuvor erwähnten Website, der Schlüsselteil des Algorithmus sei:

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

Dies scheint falsch, weil er / sie an einer Stelle sagt, dass P [i] gleich 5 ist, wenn P [i '] = 7 und P [i] nicht kleiner oder gleich R - i ist.

Wenn Sie mit dem Algorithmus nicht vertraut sind, finden Sie hier einige weitere Links:http://tristan-interview.blogspot.com/2011/11/longest-palindrome-substring-manachers.html (Ich habe es versucht, aber die Terminologie ist schrecklich und verwirrend. Erstens sind einige Dinge nicht definiert. Außerdem sind zu viele Variablen vorhanden. Sie benötigen eine Checkliste, um sich daran zu erinnern, welche Variable auf was verweist.)

Ein anderer ist:http://www.akalin.cx/längste-palindrom-lineare- zeit (Viel Glück)

Der Kern des Algorithmus besteht darin, das längste Palindrom in linearer Zeit zu finden. Es kann mit minimalem bis mittlerem Aufwand in O (n ^ 2) durchgeführt werden. Dieser Algorithmus soll ziemlich "clever" sein, um auf O (n) zu kommen.