Po spędzeniu około 6-8 godzin próbując przetrawić algorytm Manachera, jestem gotów wrzucić ręcznik. Ale zanim to zrobię, oto ostatni strzał w ciemności: czy ktoś może to wyjaśnić? Nie obchodzi mnie kod. Chcę, żeby ktoś wyjaśniłALGORYTM.

Wydaje się, że jest to miejsce, które inni najwyraźniej lubią wyjaśniać algorytm:http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

Rozumiem, dlaczego chciałbyś przekształcić ciąg, powiedzmy, „abba” na # a # b # b # a # Po tym jak zgubiłem. Na przykład autor wspomnianej wcześniej strony mówi, że kluczową częścią algorytmu jest:

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

Wydaje się to błędne, ponieważ mówi on w pewnym momencie, że P [i] jest równe 5, gdy P [i '] = 7 i P [i] jest nie mniejsze lub równe R - i.

Jeśli nie znasz algorytmu, oto kilka linków:http://tristan-interview.blogspot.com/2011/11/longest-palindrome-substring-manachers.html (Próbowałem tego, ale terminologia jest okropna i myląca. Po pierwsze, niektóre rzeczy nie są zdefiniowane. Także, zbyt wiele zmiennych. Potrzebna jest lista kontrolna, aby przypomnieć, która zmienna odnosi się do czego.)

Inny to:http://www.akalin.cx/longest-palindrome-linear-time (powodzenia)

Podstawową zasadą algorytmu jest znalezienie najdłuższego palindromu w czasie liniowym. Można to zrobić w O (n ^ 2) przy minimalnym lub średnim wysiłku. Algorytm ten ma być „sprytny”, aby sprowadzić go do O (n).