Алгоритм Апостолико-Крочемора
Алгоритм Апостолико-Крочемора (англ. Apostolico-Crochemore algorithm) - вариация Алгоритма Бойера-Мура.
Описание алгоритма
Нам даны: — текст, — образец, , .
Для начала рассмотрим ситуацию, когда мы сравниваем наш образец с . Предположим, что первое несовпадение произойдет между и при . Тогда и . Когда сдвиг возможен, разумно ожидать что префикс шаблона совпадет c некоторым суффиксом . Более того, если мы ходим избежать несовпадения при сдвиге, то нужно чтобы символ, следующий за префиксом в шаблоне, не совпадал с . Такой наибольший префикс называется помеченным бордером строки .
| Определение: |
| помеченный бордер (англ. tagged border) строки — строка . |
Введем обозначение: пусть — длина наибольшего бордера для за которым следует символ и если нет такого помеченного бордера, где (). Затем после сдвига сравнение можно продолжить между символами и не потеряв никакого вхождения в и избежав отступа по тексту (смотри рис. 1).
Псевдокод
empty
Пусть теперь , если и , иначе равно позиции первого элемента, который не равен (, где и , а и ). На каждой итерации алгоритма мы выполняем сравнения с шаблоном в следующем порядке: .
Во время поиска вхождений мы рассматриваем данную тройку где:
- шаблон сравнивается с
- и
- и
Вначале инициализируем эту тройку . Теперь опишем, как по уже вычисленной тройке перейти к следующей. Возможны три случая в зависимости от значения :
- :
- Если , тогда следующая тройка .
- Если , тогда следующая тройка .
-
- Если , тогда следующая тройка .
- Если , тогда возможны два случая в зависимости от значения :
- Если , тогда следующая тройка .
- Если , тогда следующая тройка .
- :
- Если и , тогда следующая тройка .
- Иначе либо и , либо . Если , то вхождение x в y найдено. В обоих случаях следующая тройка вычисляется как в случае .
Асимптотика алгоритма
Стадия предподсчета, а именно вычисление массива и переменной занимает времени и константное количество памяти. Этап поиска занимает времени более того алгоритм в худшем случае выполнит сравнений.
