Алгоритм Манахера #39; (алгоритм нахождения самой длинной палиндромной подстроки за линейное время)

Проведя около 6 -8 часов, пытаясь переварить алгоритм Манахера, я готов сдаться. Но прежде чем я это сделаю, вот последний выстрел в темноте :, кто-нибудь может это объяснить? Меня не волнует код. Я хочу, чтобы кто-нибудь объяснил АЛГОРИТМ .

Кажется, это то место, которое другим понравилось объяснять алгоритм: http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

Я понимаю, почему вы хотите преобразовать строку, скажем, 'abba' в #a #b #b #а #После этого я потерялся. Например, автор ранее упомянутого веб-сайта говорит, что ключевой частью алгоритма является :

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

. Это кажется неверным, потому что в какой-то момент он/она говорит, что P[i] равно 5, когда P[i'] = 7 и P [i] не меньше или равно R -i.

Если вы не знакомы с алгоритмом, вот еще несколько ссылок.:http://tristan-interview.blogspot.com/2011/11/longest-palindrome-substring-manachers.html(Я пробовал этот, но терминология ужасная и запутанная. Во-первых, некоторые вещи не определены. Кроме того, слишком много переменных. Вам нужен контрольный список, чтобы вспомнить, какая переменная на что ссылается.)

Другое:http://www.akalin.cx/longest-palindrome-linear-time(удачи)

Суть алгоритма в том, чтобы найти самый длинный палиндром за линейное время. Это можно сделать за O (n^2 )с минимальными и средними усилиями. Этот алгоритм должен быть довольно «умным», чтобы довести его до O (n ).