Алгоритм Апостолико-Крочемора
Алгоритм Апостолико — Крочемора (англ. Apostolico — Crochemore algorithm) — алгоритм поиска подстроки в строке.
Описание алгоритма
Нам даны: — текст, — образец, , .
Для начала рассмотрим ситуацию, когда мы сравниваем наш образец с . Предположим, что первое несовпадение произойдет между и при . Тогда и . Когда сдвиг возможен, разумно ожидать, что префикс шаблона совпадет c некоторым суффиксом . Более того, если мы хотим избежать несовпадения при сдвиге, то нужно, чтобы символ, следующий за префиксом в шаблоне, не совпадал с . Такой наибольший префикс называется помеченным бордером строки .
| Определение: |
| Помеченный бордер (англ. tagged border) строки — строка . |
Введем обозначение: пусть — длина наибольшего бордера для за которым следует символ и если нет такого помеченного бордера, где (). Затем, после сдвига, сравнение можно продолжить между символами и не потеряв никакого вхождения в и избежав отступа по тексту (смотри рисунок ниже).
Пусть теперь , если и , иначе равно позиции первого элемента, который не равен (, где и , а и ). На каждой итерации алгоритма мы выполняем сравнения с шаблоном в следующем порядке: .
Во время поиска вхождений мы рассматриваем данную тройку где:
- шаблон сравнивается с
- и
- и
Вначале инициализируем эту тройку . Теперь опишем, как по уже вычисленной тройке перейти к следующей. Возможны три случая в зависимости от значения :
- :
- Если , тогда следующая тройка .
- Если , тогда следующая тройка .
-
- Если , тогда следующая тройка .
- Если , тогда возможны два случая в зависимости от значения :
- Если , тогда следующая тройка .
- Если , тогда следующая тройка .
- :
- Если и , тогда следующая тройка .
- Иначе либо и , либо . Если , то вхождение в найдено. В обоих случаях следующая тройка вычисляется, как в случае .
Псевдокод
void getT(string x, int t[]):
int i = 0
int j = t[0] = -1
while i < x.size
while j > -1 and x[i] != x[j]
j = t[j]
i++
j++
if x[i] == x[j]
t[i] = t[j]
else
t[i] = j
void aG(string x, string y):
int l, t[x.size]
//предподсчет вычисление массива
getT(x, t)
for l = 1; x[l - 1] == x[l]; l++
if l == x.size
l = 0
//поиск вычисление позиций вхождения в
int i = l
int j = 0
int k = 0
while j <= y.size - x.size
while i < x.size and x[i] == y[i + j]
++i
if i >= x.size
while k < l and x[k] == y[j + k]
++k
if k >= l
OUTPUT(j)
j += i - t[i]
if i == l
k = max(0, k - 1)
else
if t[i] <= l
k = max(0, t[i])
i = l
else
k = l
i = t[i]
Асимптотика алгоритма
Этап предподсчета, а именно вычисление массива и переменной занимает времени и константное количество памяти. Этап поиска занимает времени, более того, алгоритм в худшем случае выполнит сравнений.
