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