74
правки
Изменения
Начало - описание без псевдокода и примера
'''Двусторонний алгоритм''' (англ. ''Two Way algorithm'') — алгоритм [[Наивный алгоритм поиска подстроки в строке#Постановка задачи|поиска подстроки в строке]].
==Характерные черты==
* требует упорядоченный алфавит
* этап предобработки занимает <math>O(m)</math> времени и константное количество памяти
* этап поиска за время <math>O(n)</math>
* в худшем случае производится <math>2n - m</math> сравнений символов
==Описание алгоритма==
Образец <tex>x</tex> разбивается на две части <math>x_l</math> и <math>x_r</math> так, что <math>x=</math> <math>x_l</math> <math>x_r</math>. Затем фаза поиска в двустороннем алгоритме состоит в сравнении символов <math>x_r</math> слева направо, и затем, если на этом первом этапе не происходит несовпадений, в сравнении символов <math>x_l</math> справа налево (второй этап).
Фаза предобработки, таким образом, заключается в поиске подходящего разбиения <math>x_l</math> <math>x_r</math>.
{{Определение
|definition = Пусть <math>(u, v)</math> {{---}} разбиение <math>x</math>. '''Повторение''' в <math>(u, v)</math> {{---}} слово <math>w</math> такое, что для него выполнены следующие условия:
# <math>w</math> {{---}} суффикс <math>u</math> или <math>u</math> {{---}} суффикс <math>w</math>;
# <math>w</math> {{---}} префикс <math>v</math> или <math>v</math> {{---}} префикс <math>w</math>.
Иными словами, <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 <= r(u, v) <= |x|</math>
Разбиение x на <math>(u, v)</math> такое, что <math>r(u, v) = per(x)</math> называется '''критическим разбиением''' <math>x</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><=</math> и максимальный суффикс <math>z~</math> для обратного порядка <math><=~</math>. Затем <math>(x_l, x_r)</math> выбираются так, что <math>|x_l| = max{|z|, |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>.
Такие действия приводят к квадратичной работе алгоритма в худшем случае, но этого можно избежать запоминанием префикса: когда производится сдвиг длиной <math>per(x)</math>, длина совпадающего префикса образца в начале "окна" (а именно <math>m - per(x)</math>) после сдвига запоминается, чтобы не просматривать ее заново при следующем проходе.
Фаза поиска может быть выполнена за время <math>O(n)</math>.
Двусторонний алгоритм производит <math>2n - m</math> сравнений символов в худшем случае; вариация этого алгоритма от Бреслера (Breslauer) выполняет менее <math>2n - m</math> сравнений и использует константное количество памяти.
==Псевдокод==
==Характерные черты==
* требует упорядоченный алфавит
* этап предобработки занимает <math>O(m)</math> времени и константное количество памяти
* этап поиска за время <math>O(n)</math>
* в худшем случае производится <math>2n - m</math> сравнений символов
==Описание алгоритма==
Образец <tex>x</tex> разбивается на две части <math>x_l</math> и <math>x_r</math> так, что <math>x=</math> <math>x_l</math> <math>x_r</math>. Затем фаза поиска в двустороннем алгоритме состоит в сравнении символов <math>x_r</math> слева направо, и затем, если на этом первом этапе не происходит несовпадений, в сравнении символов <math>x_l</math> справа налево (второй этап).
Фаза предобработки, таким образом, заключается в поиске подходящего разбиения <math>x_l</math> <math>x_r</math>.
{{Определение
|definition = Пусть <math>(u, v)</math> {{---}} разбиение <math>x</math>. '''Повторение''' в <math>(u, v)</math> {{---}} слово <math>w</math> такое, что для него выполнены следующие условия:
# <math>w</math> {{---}} суффикс <math>u</math> или <math>u</math> {{---}} суффикс <math>w</math>;
# <math>w</math> {{---}} префикс <math>v</math> или <math>v</math> {{---}} префикс <math>w</math>.
Иными словами, <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 <= r(u, v) <= |x|</math>
Разбиение x на <math>(u, v)</math> такое, что <math>r(u, v) = per(x)</math> называется '''критическим разбиением''' <math>x</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><=</math> и максимальный суффикс <math>z~</math> для обратного порядка <math><=~</math>. Затем <math>(x_l, x_r)</math> выбираются так, что <math>|x_l| = max{|z|, |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>.
Такие действия приводят к квадратичной работе алгоритма в худшем случае, но этого можно избежать запоминанием префикса: когда производится сдвиг длиной <math>per(x)</math>, длина совпадающего префикса образца в начале "окна" (а именно <math>m - per(x)</math>) после сдвига запоминается, чтобы не просматривать ее заново при следующем проходе.
Фаза поиска может быть выполнена за время <math>O(n)</math>.
Двусторонний алгоритм производит <math>2n - m</math> сравнений символов в худшем случае; вариация этого алгоритма от Бреслера (Breslauer) выполняет менее <math>2n - m</math> сравнений и использует константное количество памяти.
==Псевдокод==
