299
правок
Изменения
→Решение (алгоритм Манакера)
* Рассмотрим случай, когда <tex>i \le r</tex>. Попробуем извлечь часть информации из уже подсчитанных значений <tex>d_1[]</tex>. А именно, отразим позицию <tex>i</tex> внутри палиндрома <tex>(l,r)</tex>, т.е. получим позицию <tex>j=l+(r-i)</tex>, и рассмотрим значение <tex>d_1[j]</tex>. Поскольку <tex>j</tex> — позиция, симметричная позиции <tex>i</tex>, то почти всегда можно просто присвоить <tex>d_1[i]=d_1[j]</tex>. Иллюстрация этого отражения (палиндром вокруг фактически "копируется" в палиндром вокруг <tex>i</tex>):'''IMG1'''
Однако здесь есть тонкость, которую надо обработать правильно: когда "внутренний палиндром" достигает границы внешнего или вылазит за неё, т.е. <tex>j-d_1[j]+1 \le l</tex> (или, что то же самое, <tex>i+d_1[j]-1 \ge r</tex>). Поскольку за границами внешнего палиндрома никакой симметрии не гарантируется, то просто присвоить <tex>d_1[i]=d_1[j]</tex> будет уже некорректно: у нас недостаточно сведений, чтобы утверждать, что в позиции <tex>i</tex> палиндром имеет такую же длину.
На самом деле, чтобы правильно обрабатывать такие ситуации, надо "обрезать" длину палиндрома, т.е. присвоить <tex>d_1[i]=r-i</tex>. После этого следует пустить тривиальный алгоритм, который будет пытаться увеличить значение <tex>d_1[i]</tex>, пока это возможно.
Иллюстрация этого случая (на ней палиндром с центром в <tex>j</tex> изображен уже "обрезанным" до такой длины, что он впритык помещается во внешний палиндром): '''IMG2'''
В завершение описания алгоритма сталось только напомнить, что надо не забывать обновлять значения <tex>(l,r)</tex> после вычисления очередного значения <tex>d_1[i]</tex>.
Также повторимся, что выше описано рассуждение для вычисления массива нечётных палиндромов <tex>d_1[]</tex>; для массива чётных палиндромов <tex>d_2[]</tex> все рассуждения аналогичны.
== См. также ==
