Алгоритм Колусси — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
м
Строка 90: Строка 90:
 
* [http://www-igm.univ-mlv.fr/~lecroq/string/node10.html Colussi algorithm]
 
* [http://www-igm.univ-mlv.fr/~lecroq/string/node10.html Colussi algorithm]
 
* [http://alg.csie.ncnu.edu.tw/course/StringMatching/Colussi.ppt Colussi.ppt]
 
* [http://alg.csie.ncnu.edu.tw/course/StringMatching/Colussi.ppt Colussi.ppt]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Поиск подстроки в строке]]

Версия 00:06, 15 мая 2014

Алгоритм

Отметим, что нумерация символов строк и элементов массива у нас начинается с [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]




Псевдокод

Наивный вариант

  int[] buildHmax(char[] x, int m):
     int hmax[m + 1]
     for k = 1 .. m
        int i = k
        while x[i] == x[i - k]
           i++
        hmax[k] = i
     return hmax

Явная реализация по определению, очевидно, работает за [math]O(m^2)[/math] и требует [math]O(m)[/math] памяти.

Улучшенный вариант

  int[] buildHmax(char[] x, int m):
     int hmax[m + 1]
     int i = 1
     int k = 1
     while k <= m
        while x[i] == x[i - k]
           i++;
        hmax[k] = i
        int q = k + 1
        while hmax[q - k] + k < i
           hmax[q] = hmax[q - k] + k
           q++
        k = q
        if k == i + 1
           i = k
     return hmax

На каждой итерации цикла увеличивается либо переменная [math]i[/math], либо [math]k[/math] (или переменная [math]q[/math], которая используется в конечном счете для обновления [math]k[/math]). Поскольку [math]i = 1[/math] и [math]k = 1[/math] в начале и [math]i \lt k = m + 1[/math] в конце алгоритма, количество итераций алгоритма не превосходит [math]2 \cdot m[/math]. Следовательно функция требует [math]O(m)[/math] времени и памяти.

Функция для построения массива [math]Kmin[/math].

  int[] buildKmin(int[] hmax, int m)
     int kmin[m]
     for i = m .. 1
        if hmax[i] < m
           kmin[hmax[i]] = i
     return kmin

Функция для построения массива [math]Rmin[/math].

  int[] buildRmin(int[] hmax, int[] kmin, int m)
     int rmin[m]
     int r = 0
     for i = m - 1 .. 0
        if hmax[i + 1] == m
           r = i + 1
        if kmin[i] == 0
           rmin[i] = r
        else
           rmin[i] = 0
     return rmin

Асимптотики

  • 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.

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

Достоинства

Недостатки

Ссылки