Потратив около 6-8 часов, пытаясь переварить алгоритм Манахера, я готов бросить полотенце. Но прежде чем я это сделаю, вот последний выстрел в темноте: кто-нибудь может это объяснить? Я не забочусь о коде. Я хочу, чтобы кто-то объяснилALGORITHM.

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

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

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

Это кажется неправильным, потому что он / она в какой-то момент говорит, что 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).