59
правок
Изменения
→Пример
==Описание алгоритма==
Нам даны: <tex>y</tex> {{---}} текст, <tex>x</tex> {{---}} образец, <tex>m {{=}} |x|</tex>, <tex>n {{=}} |y|</tex>.
Для начала рассмотрим ситуацию, когда мы сравниваем наш образец с <tex>y[j \ldots j + m - 1]</tex>. Предположим, что первое несовпадение произойдет между <tex>x[i]</tex> и <tex>\neq y[i + j]</tex> при <tex>0 < i < m</tex>. Тогда <tex>x[0 \ldots i - 1] {{=}} y[j \ldots i + j - 1] {{=}} u</tex> и <tex>a {{=}} x[i] \neq y[i + j] {{=}} b</tex>.
Когда сдвиг возможен, разумно ожидать, что префикс <tex>v</tex> шаблона совпадет c некоторым суффиксом <tex>u</tex>. Более того, если мы хотим избежать несовпадения при сдвиге, то нужно, чтобы символ, следующий за префиксом <tex>v</tex> в шаблоне, не совпадал с <tex>a</tex>. Такой наибольший префикс <tex>v</tex> называется '''помеченным бордером''' строки <tex>u</tex>.
{{Определение
|id=tagged border
|definition='''помеченный Помеченный бордер''' (англ. ''tagged border'') строки <tex>\beta</tex> {{---}} строка <tex>\alpha : \forall i = 1 \ldots n - 1, \alpha[i] {{=}} \beta[i + (m - n)], \alpha[n] \neq \beta[m], n {{=}} |\alpha|, m {{=}} |\beta|</tex>.
}}
Введем обозначение: пусть <tex>t[i]</tex> {{---}} длина наибольшего бордера для <tex>x[0 .. i - 1]</tex> за которым следует символ <tex>c \neq x[i]</tex> и <tex>-1</tex> если нет такого помеченного бордера, где <tex>0 < i \le leqslant m</tex> (<tex>t[0] = -1</tex>). Затем, после сдвига, сравнение можно продолжить между символами <tex>x[t[i]]</tex> и <tex>y[i + j]</tex> не потеряв никакого вхождения <tex>x</tex> в <tex>y</tex> и избежав отступа по тексту (смотри рисрисунок ниже). [[Файл:Apostolico-Crochemore-Shifts.png]] Примечание: <tex>v</tex> {{---}} помеченный бордер строки <tex>u</tex>. Пусть теперь <tex>l = 0</tex>, если <tex>x = c ^ m</tex> и <tex>c \in \Sigma</tex>, иначе <tex>l</tex> равно позиции первого элемента, который не равен <tex>x[0]</tex> (<tex>x = a ^ l bu</tex>, где <tex>a \in \Sigma</tex>, <tex>b \in \Sigma</tex>, <tex>a \neq b</tex>, <tex>u \in \Sigma^*</tex>). При каждой подстановке шаблона к тексту к позиции <tex>i</tex> мы проводим следующие сравнения: <tex>x[l] = y[i + l], x[l + 1] = y[i + l + 1], \ldots , x[m - 2] = y[i + m - 2], x[m - 1] = y[i + m - 1],</tex><tex> x[0] = y[i], x[1] = y [i + 1)], \ldots , x[l - 1] = y[i + l - 1]</tex>.
Во время поиска вхождений мы рассматриваем данную тройку <tex>(i, j, k)</tex> где:
* шаблон сравнивается с <tex>y[j, \ldots , j + m - 1]</tex>
* <tex>0 \le leqslant k \le leqslant l</tex> и <tex>x[0, \ldots, k - 1] {{=}} y[j, \ldots , j + k - 1]</tex>* <tex>l \le leqslant i < m</tex> и <tex>x[l, \ldots, i - 1] {{=}} y[j + l, \ldots , i + j - 1]</tex>(см. рисунок ниже)
Вначале инициализируем эту тройку <tex>(l, 0, 0)</tex>.
Теперь опишем, как по уже вычисленной тройке <tex>(i, j, k)</tex> перейти к следующей.
# <tex>i = l</tex>:
#: Если <tex>x[i] {{=}} y[i + j]</tex>, тогда следующая тройка <tex>(i + 1, j, k)</tex>.
#: Если <tex>x[i] \neq y[i + j]</tex>, тогда следующая тройка <tex>(l, j + 1, \max(0, k - 1))</tex>.
# <tex>l < i < m </tex>
#: Если <tex>x[i] {{=}} y[i + j]</tex>, тогда следующая тройка <tex>(i + 1, j, k)</tex>.
#: Если <tex>x[i] \neq y[i + j]</tex>, тогда возможны два случая в зависимости от значения <tex>t[i]</tex>:
#:* Если <tex>t[i] \le leqslant l</tex>, тогда следующая тройка <tex>(l, i + j - t[i], \max(0, t[i]))</tex>.
#:* Если <tex>t[i] > l</tex>, тогда следующая тройка <tex>(t[i], i + j - t[i], l)</tex>.
# <tex>i = m</tex>:
#: Если <tex> k < l </tex> и <tex>x[k] {{=}} y[j + k]</tex>, тогда следующая тройка <tex>(i, j, k + 1)</tex>.
#: Иначе либо <tex>k < l</tex> и <tex>x[k] \ne y[l + k]</tex>, либо <tex>k = l</tex>. Если <tex>k = l</tex>, то вхождение <tex>x</tex> в <tex>y</tex> найдено. В обоих случаях следующая тройка вычисляется, как в случае <tex>l < i < m </tex>.
==Асимптотика алгоритма==
==См. также==
==Источники информации==
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Поиск подстроки в строке]]
[[Категория:Точный поиск]]