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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Псевдокод)
Строка 39: Строка 39:
  
 
===Псевдокод===
 
===Псевдокод===
−
     empty
+
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()]
 +
    <font color=green>//предподсчет <tex>-</tex> вычисление массива <tex>t</tex></font>
 +
    getT(x, t)
 +
    for l = 1 x[l - 1] == x[l] l++
 +
        if l == x.size()
 +
            l = 0
 +
    <font color=green>//поиск<tex>-</tex> вычисление позиций вхождения <tex>x</tex> в <tex>y</tex></font>
 +
    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]
  
 
==Асимптотика алгоритма==
 
==Асимптотика алгоритма==

Версия 23:41, 4 марта 2016

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

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

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

Нам даны: [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).

Пусть теперь [math]l {{=}} 0[/math], если [math]x = c ^ m[/math] и [math]c \in \Sigma[/math], иначе [math]l[/math] равно позиции первого элемента, который не равен [math]x[0][/math] ([math]x {{=}} a ^ l bu[/math], где [math]a[/math] и [math]b \in \Sigma[/math], а [math]u \in \Sigma^*[/math] и [math]a \neq b[/math]). На каждой итерации алгоритма мы выполняем сравнения с шаблоном в следующем порядке: [math]l, l + 1, \ldots , m - 2, m - 1, 0, 1, \ldots , l - 1[/math].

Во время поиска вхождений мы рассматриваем данную тройку [math](i, j, k)[/math] где:

  • шаблон сравнивается с [math]y[j, \ldots , j + m - 1][/math]
  • [math]0 \le k \le l[/math] и [math]x[0, \ldots, k - 1] {{=}} y[j, \ldots , j + k - 1][/math]
  • [math]l \le i \lt m[/math] и [math]x[l, \ldots, i - 1] {{=}} y[j + l, \ldots , i + j - 1][/math]

Вначале инициализируем эту тройку [math](l, 0, 0)[/math]. Теперь опишем, как по уже вычисленной тройке [math](i, j, k)[/math] перейти к следующей. Возможны три случая в зависимости от значения [math]i[/math]:

  1. [math]i = l[/math]:
    Если [math]x[i] {{=}} y[i + j][/math], тогда следующая тройка [math](i + 1, j, k)[/math].
    Если [math]x[i] \neq y[i + j][/math], тогда следующая тройка [math](l, j + 1, \max(0, k - 1))[/math].
  2. [math]l \lt i \lt m [/math]
    Если [math]x[i] {{=}} y[i + j][/math], тогда следующая тройка [math](i + 1, j, k)[/math].
    Если [math]x[i] \neq y[i + j][/math], тогда возможны два случая в зависимости от значения [math]t[i][/math]:
    • Если [math]t[i] \le l[/math], тогда следующая тройка [math](l, i + j - t[i], \max(0, t[i]))[/math].
    • Если [math]t[i] \gt l[/math], тогда следующая тройка [math](t[i], i + j - t[i], l)[/math].
  3. [math]i = m[/math]:
    Если [math] k \lt l [/math] и [math]x[k] {{=}} y[j + k][/math], тогда следующая тройка [math](i, j, k + 1)[/math].
    Иначе либо [math]k \lt l[/math] и [math]x[k] \ne y[l + k][/math], либо [math]k = l[/math]. Если [math]k = l[/math], то вхождение x в y найдено. В обоих случаях следующая тройка вычисляется, как в случае [math]l \lt i \lt m [/math].

Псевдокод

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()]
   //предподсчет [math]-[/math] вычисление массива [math]t[/math]
   getT(x, t)
   for l = 1 x[l - 1] == x[l] l++
       if l == x.size() 
           l = 0
   //поиск[math]-[/math] вычисление позиций вхождения [math]x[/math] в [math]y[/math]
   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]

Асимптотика алгоритма

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

См. также

Источники информации

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Апостолико-Крочемора&oldid=52407»