Как выбрать следующий центр в самом длинном алгоритме палиндром?

Question

Это вопрос о Самый длинный алгоритм палиндрома обсуждал здесь некоторое время назад. Цитируется Сообщение блога, что объясняет алгоритм, говорит: «Чтобы выбрать следующий центр, возьмите центр самого длинного палиндромного суффикса текущего палиндрома». Анкет К сожалению, они не предоставляют доказательства, и я не очень понимаю Почему Следующий центр Центр самого длинного палиндромного суффикса нынешнего палиндрома.

Кто -нибудь может доказать/объяснить это?

Answer 1

Итак, мы движемся вправо ...

Скажите, что ваш «текущий» палиндром - 40 букв. (Может быть, сосредоточен на положении 100.) Вы пытаетесь найти более крупную.

(Хорошо, может быть более крупный, длиной 900 букв, и это 50 000 букв справа - совершенно не взволнованный с этим. Это нормально. Но мы доберемся до этого в будущем. Пока, у нас есть Чтобы переместить центр вправо, в поисках дольше, чем палиндромы, имеет смысл?)

Таким образом, мы должны двигаться вправо - мы могли бы двигаться на один шаг. Но мы хотим двигаться как можно дальше, не пропуская.

Теперь, если следующий справа будет включать этот ... на самом деле, он должен включать в себя самого правого письма из этой группы 40. (это не может быть дальше влево, как мы уже проверили, поэтому она должна центрироваться после 100, и, потому что это будет дольше 40, это должно Включите наше правое письмо, #120.)

Так как далеко нам нужно идти?

Ну, ты не можешь вернуться (от 120) дальше, чем палиндрома! Если в середине это не палиндром, это никогда не будет палиндром.

3333333333333331110111

Вы можете только «обратно» к 0. 1, сидящий слева от 0 (например), никогда не может быть палиндром.

Так что это так просто. Вы должны включить нашу самую правую букву (Если мы собираемся включить любого из нас вообще), и вы хотите, чтобы это было максимально большим, как можно больше, и это должно быть палиндромом, потому что палиндром может только начать (я имею в виду «со середины») с палиндромами.

В приведенном выше примере невозможно, чтобы 1 слева или 0, или, скажем, правое значение 3, когда-нибудь в этой вселенной центре палиндрома, независимо от того, что мы позже найдем справа. У них нет палиндромов вокруг них, поэтому они никогда не могут быть »центром палиндрома!

Обратите внимание, что 3 в середине 3 -х годов могут сосредоточиться на большей палиндроме .... но Не забывайте, что мы уже проверили, что это самый длинный палиндром до сих пор (на основе центров, слева), так что это не может быть правдой.

Таким образом, любой палиндром, который длиннее этого - скорее, следующая возможная отправная точка для палиндрома дольше, чем этот - это 0.

Другими словами, это просто центр самого большого палиндрома, который у нас сейчас есть. (Итак, не «111», который является палиндром, но коротким, но «1110111», который является самым длинным палиндром, который вы можете увидеть справа.)

Действительно, две возможности, которые мы должны проверить,-это (а) «0» и (б) «1» в втором месте. Конечно, среди этих двух возможностей мы должны идти слева направо, поэтому (а) «0» действительно является следующим, чтобы проверить.

Не забывайте, что эти двое (0 и 1 рассматриваемые) эквивалентны сказанию: «До конца придерживается палиндрома 1110111, и к концу придерживается более короткая палиндром 111».

Конечно, 1110111 длиннее, поэтому центр 1110111, очевидно, находится слева от центра 111.

Самый длинный палиндром застрял вправо, конечно, будет центр ближе всего к левой.

Надеюсь, это ясно показывает только конкретную часть обсуждения в связанном блоге, о котором вы спрашивали !!! Я сознательно повторил себя несколькими способами, надеюсь, это поможет. Это День юнгианских алгоритмов :)

Еще раз обратите внимание, что я специально и только пытаюсь уточнить очень конкретную проблему, о которой спросил Майкл.

Кровавый сбивает с толку, а?

Кстати, я просто проигнорировал проблему за не все-характерные центры, но это не имеет отношения к пониманию того, о чем вы спрашивали.