74
правки
Изменения
Нет описания правки
==Описание алгоритма==
Фаза предобработки, таким образом, заключается в поиске подходящего разбиения <math>x_l</math> <math>x_r</math>.
{{Определение
Если <math>(u, v)</math> {{---}} критическое разбиение <math>x</math>, то на позиции <math>|u|</math> в <math>x</math> общий и локальный периоды одинаковы. Двусторонний алгоритм находит критическое разбиение <math>(x_l, x_r)</math> такое, что <math>|x_l| < per(x)</math> и длина <math>|x_l|</math> минимальна.
Чтобы найти критическое разбиение <math>(x_l, x_r)</math> мы сперва вычислим <math>z</math> {{---}} максимальный суффикс <math>x</math> в порядке <math>\leqslant</math> и максимальный суффикс <math>\widetilde{z~}</math> для обратного порядка <math>\geqslant</math>. Затем <math>(x_l, x_r)</math> выбираются так, что <math>|x_l| = \max(|z|, |\widetilde{z~}|)</math>.
Фаза предобработки может быть выполнена за время O(m) и константное количество памяти.
Фаза поиска в двустороннем алгоритме состоит из сравнения символов <math>x_r</math> слева направо и символов <math>x_l</math> справа налево. Когда происходит несовпадение при просмотре <math>k</math>-го символа в <math>x_r</math>, производится сдвиг длиной <math>k</math>. Когда происходит несовпадение при просмотре <math>x_l</math>, или когда образец встретился в строке, производится сдвиг длиной <math>per(x)</math>.
