299
правок
Изменения
→Алгоритм Манакера
* Если <tex>i</tex> не находится в пределах текущего палиндрома, т.е. <tex>i>r</tex>, то просто выполним тривиальный алгоритм. Т.е. будем последовательно увеличивать значение <tex>d_1[i]</tex>, и проверять каждый раз — правда ли текущая подпоследовательность <tex>[i-d_1[i];i+d_1[i]]</tex> является палиндромом. Когда найдем первое расхождение, либо когда дойдем до границ строки <tex>S</tex> — останавливаемся: окончательно посчитали значение <tex>d_1[i]</tex>. После этого мы должны не забыть обновить значения <tex>(l,r)</tex>.
* Рассмотрим случай, когда <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>. Иллюстрация этого отражения ( [[Файл:Palindrome1.png|300px|thumb|right|палиндром вокруг фактически "копируется" в палиндром вокруг <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>(l,r)</tex> после вычисления очередного значения <tex>d_1[i]</tex>.
