Алгоритм Колусси

Материал из Викиконспекты
Перейти к: навигация, поиск

Алгоритм

Отметим, что нумерация символов строк и элементов массива у нас начинается с [math]0[/math].

Сначала построим массивы: Kmp, Kmin, Rmin, Shift.


Определение:
Обозначим за [math]\mathrm{Kmin}(i)=i - \mathrm{Kmp}(i)[/math] функцию, возвращающую количество прыжков для позиций [math]i[/math], которые являются полными.


Определение:
Обозначим за [math]\mathrm{Rmin}(i)[/math] функцию, возвращающую наименьший из периодов шаблона, которые больше позиции [math]i[/math], для позиций, которые являются пустыми.


Определение:
Функция сдвига [math]\mathrm{Shift}(i) = \begin{cases} \mathrm{Rmin}(i), & \mbox{if } \mathrm{Kmp}(i) = -1\\ \mathrm{Kmin}(i), & \mbox{otherwise} \end{cases}[/math]




Псевдокод

Асимптотики

  • partitions the set of pattern positions into two disjoint subsets; the positions in the first set are scanned from left to right and when no mismatch occurs the positions of the second subset are scanned from right to left;
  • preprocessing phase in [math]O(m)[/math] time and space complexity;
  • searching phase in [math]O(n)[/math] time complexity;
  • performs [math]3/2n[/math] text character comparisons in the worst case.

Сравнение с другими алгоритмами

Достоинства

Недостатки

Ссылки