Это вопрос о самом длинном алгоритме палиндрома Обсуждали здесь некоторое время назад. Цитируемое сообщение в блоге < / a>, который объясняет алгоритм, говорит: "чтобы выбрать следующий центр, возьмите центр самого длинного палиндромного суффикса текущего палиндрома". К сожалению, они не предоставляют доказательства, и я действительно не понимаю, почему следующий центр является центром самого длинного палиндромного суффикса текущего палиндрома.
Кто-нибудь может это доказать / объяснить?
Так что движемся вправо ...
Допустим, ваш «текущий» палиндром состоит из 40 букв. (Может быть, в центре, скажем, позиции 100). Вы пытаетесь найти более крупную позицию.
(Хорошо, может быть более крупный, длиной 900 букв, и это 50 000 букв справа - совершенно не связанный с этим. Ничего страшного. Но мы вернемся к этому в будущем. На данный момент у нас есть перемещать центр вправо при поиске палиндромов длиной более 40. Имеет смысл?)
Итак, мы должны двигаться вправо - мы могли бы двигаться на один шаг. НО мы хотим продвинуться как можно дальше, не пропуская ни одного.
Теперь, если следующая справа будет включать эту ... на самом деле, она должна включать самую правую букву из этой группы из 40. (Он не может быть левее, как мы уже проверили, поэтому он должен располагаться в центре после 100, и, поскольку он будет длиннее 40 , он должен включать нашу правую букву, # 120.)
Итак, как далеко нам нужно идти?
Что ж, вы не можете вернуться (со 120) дальше палиндрома! Если это не палиндром посередине, он никогда не будет палиндромом.
3333333333333331110111
Вы можете только «вернуться» к 0. 1, стоящая слева от 0 (например), никогда не может быть палиндромом.
Так что все просто. Вы должны включить нашу крайнюю правую букву (если мы вообще собираемся включать кого-либо из нас), и, если вы хотите, чтобы она была как можно больше, и это должен быть палиндром, потому что палиндромы могут начинаться (я имею в виду «с середины») только с палиндромов.
в приведенном выше примере невозможно, чтобы 1 слева или 0, или, скажем, крайняя правая 3, могли когда-либо в этой вселенной центрировать палиндром, независимо от того, что мы позже обнаружим справа. Вокруг них нет палиндромов, поэтому они «никогда не могут быть» центром палиндрома!
Обратите внимание, что тройка в середине тройки могла бы быть центром более крупного палиндрома .... но не забывайте, что мы уже проверили, что это самый длинный палиндром, поэтому далеко (по центрам слева), так что это не может быть правдой.
Таким образом, любой палиндром, который длиннее этого - скорее, следующая возможная отправная точка для палиндрома длиннее этого - это 0.
Другими словами, это просто центр самого большого палиндрома, который у нас сейчас есть справа. (так что не «111», который является палиндромом, но короткий, а «1110111», который является самым длинным палиндромом, который вы видите застрявшим справа.)
В самом деле, мы должны проверить две возможности: (A) «0» и (B) «1» на втором-последнем месте. конечно, среди этих двух возможностей мы должны идти слева направо, так что (A) «0» действительно следующий, который нужно проверить.
Не забывайте, что эти два (0 и 1, о которых идет речь) эквивалентны высказыванию «есть палиндром 1110111, прилипший к концу, и есть более короткий палиндром 111, прилипший к концу».
Конечно, 1110111 длиннее, поэтому центр 1110111, очевидно, находится слева от центра 111.
Самый длинный палиндром, прикрепленный справа, конечно, будет иметь центр ближе всего к левому краю.
Надеюсь, это проясняет ТОЛЬКО конкретную часть обсуждения в связанном блоге, о котором вы спрашивали !!! Я намеренно повторял себя разными способами, надеюсь, это поможет. Настал день юнгианских алгоритмов :)
Опять же, обратите внимание, что я конкретно и только пытаюсь прояснить очень конкретную проблему, о которой задал Майкл.
Чертовски запутанно, а?
Кстати, я просто проигнорировал вопрос о персонажах вне персонажей - но это не имеет отношения к пониманию того, о чем вы спрашивали.
