74
правки
Изменения
Нет описания правки
Иными словами, <math>w</math> встречается по обе стороны границы между <math>u</math> и <math>v</math> и может "залезать" (overflow). Длина повторения в <math>(u, v)</math> называется '''локальным периодом'''; наименьший локальный период записывается как <math>r(u, v)</math>.
Каждое разбиение <math>x</math> на <math>(u, v)</math> имеет как минимум одно повторение. Очевидно, что <math>1 <= \ge r(u, v) <= \ge |x|</math>
Разбиение x на <math>(u, v)</math> такое, что <math>r(u, v) = per(x)</math> называется '''критическим разбиением''' <math>x</math>.
}}
Такие действия приводят к квадратичной работе алгоритма в худшем случае, но этого можно избежать запоминанием префикса: когда производится сдвиг длиной <math>per(x)</math>, длина совпадающего префикса образца в начале "окна" (а именно <math>m - per(x)</math>) после сдвига запоминается, чтобы не просматривать ее заново при следующем проходе.
Фаза поиска может быть выполнена за время <math>O(n)</math>.
Двусторонний алгоритм производит <math>2n - m</math> сравнений символов в худшем случае; вариация этого алгоритма от Бреслера Бреслауэра (Breslauer) выполняет менее <math>2n - m</math> сравнений и использует константное количество памяти.
==Псевдокод==
