Алгоритм Апостолико-Крочемора

Эта статья находится в разработке!

Алгоритм Апостолико-Крочемора (англ. Apostolico-Crochemore algorithm) - вариация Алгоритма Бойера-Мура.

Характерные черты

• этап предобработки занимает [math]O(m)[/math] времени и константное количество памяти,
• этап поиска занимает [math]O(n)[/math] времени,
• выполняет [math]\frac{3}{2} n[/math] сравнений в худшем случае.

Описание алгоритма

Нам даны: [math]y[/math] — текст, [math]x[/math] — образец, [math]m {{=}} |x|[/math], [math]n {{=}} |y|[/math].

Для начала рассмотрим ситуацию, когда мы сравниваем наш образец с [math]y[j \ldots j + m - 1][/math]. Предположим, что первое несовпадение произойдет между [math]x[i][/math] и [math]y[i + j][/math] при [math]0 \lt i \lt m[/math]. Тогда [math]x[0 \ldots i - 1] {{=}} y[j \ldots i + j - 1] {{=}} u[/math] и [math]a {{=}} x[i] \neq y[i + j] {{=}} b[/math]. Когда сдвиг возможен, разумно ожидать что префикс [math]v[/math] шаблона совпадет c некоторым суффиксом [math]u[/math]. Более того, если мы ходим избежать несовпадения при сдвиге, то нужно чтобы символ, следующий за префиксом [math]v[/math] в шаблоне, не совпадал с [math]a[/math]. Такой наибольший префикс [math]v[/math] называется помеченным бордером строки [math]u[/math].

Определение:

помеченный бордер (англ. tagged border) строки [math]\beta[/math] — строка [math]\alpha : \forall i = 1 \ldots n - 1, \alpha[i] {{=}} \beta[i + (m - n)], \alpha[n] \neq \beta[m], n {{=}} |\alpha|, m {{=}} |\beta|[/math].

Введем обозначение: пусть [math]t[i][/math] — длина наибольшего бордера для [math]x[0 .. i - 1][/math] за которым следует символ [math]c \neq x[i][/math] и [math]-1[/math] если нет такого помеченного бордера, где [math]0 \lt i \le m[/math] ([math]t[0] = -1[/math]). Затем после сдвига сравнение можно продолжить между символами [math]x[t[i]][/math] и [math]y[i + j][/math] не потеряв никакого вхождения [math]x[/math] в [math]y[/math] и избежав отступа по тексту (смотри рис. 1).