Изменения

{{в разработке}}'''Алгоритм Апостолико-— Крочемора''' (англ. ''Apostolico-— Crochemore algorithm'') - вариация — алгоритм [[Алгоритм Бойера-МураПоиск подстроки в строке|Алгоритма Бойера-Мурапоиска подстроки в строке]].

Нам даны: <tex>y</tex> {{---}} текст, <tex>x</tex> {{---}} образец, <tex>m {{=}} |x|</tex>, <tex>n {{=}} |y|</tex>.

Для начала рассмотрим ситуацию, когда мы сравниваем наш образец с <tex>y[j \ldots j + m - 1]</tex>. Предположим, что первое несовпадение произойдет между <tex>x[i]</tex> и <tex>\neq y[i + j]</tex> при <tex>0 < i < m</tex>. Тогда <tex>x[0 \ldots i - 1] {{=}} y[j \ldots i + j - 1] {{=}} u</tex> и <tex>a {{=}} x[i] \neq y[i + j] {{=}} b</tex>. Когда сдвиг возможен, разумно ожидать , что префикс <tex>v</tex> шаблона совпадет c некоторым суффиксом <tex>u</tex>. Более того, если мы ходим хотим избежать несовпадения при сдвиге, то нужно , чтобы символ, следующий за префиксом <tex>v</tex> в шаблоне, не совпадал с <tex>a</tex>. Такой наибольший префикс <tex>v</tex> называется '''помеченным бордером''' строки <tex>u</tex>.

|definition='''помеченный Помеченный бордер''' (англ. ''tagged border'') строки <tex>\beta</tex> {{---}} строка <tex>\alpha : \forall i = 1 \ldots n - 1, \alpha[i] {{=}} \beta[i + (m - n)], \alpha[n] \neq \beta[m], n {{=}} |\alpha|, m {{=}} |\beta|</tex>.

Введем обозначение: пусть <tex>t[i]</tex> {{---}} длина наибольшего бордера для <tex>x[0 .. i - 1]</tex> за которым следует символ <tex>c \neq x[i]</tex> и <tex>-1</tex> если нет такого помеченного бордера, где <tex>0 < i \le leqslant m</tex> (<tex>t[0] = -1</tex>). Затем , после сдвига , сравнение можно продолжить между символами <tex>x[t[i]]</tex> и <tex>y[i + j]</tex> не потеряв никакого вхождения <tex>x</tex> в <tex>y</tex> и избежав отступа по тексту (смотри рис. 1рисунок ниже).

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

* <tex>0 \le leqslant k \le leqslant l</tex> и <tex>x[0, \ldots, k - 1] {{=}} y[j, \ldots , j + k - 1]</tex>* <tex>l \le leqslant i < m</tex> и <tex>x[l, \ldots, i - 1] {{=}} y[j + l, \ldots , i + j - 1]</tex>(см. рисунок ниже) 

#: Если <tex>x[i] {{=}} y[i + j]</tex>, тогда следующая тройка <tex>(i + 1, j, k)</tex>.

#: Если <tex>x[i] {{=}} y[i + j]</tex>, тогда следующая тройка <tex>(i + 1, j, k)</tex>.

#:* Если <tex>t[i] \le leqslant l</tex>, тогда следующая тройка <tex>(l, i + j - t[i], \max(0, t[i]))</tex>.

#: Если <tex> k < l </tex> и <tex>x[k] {{=}} y[j + k]</tex>, тогда следующая тройка <tex>(i, j, k + 1)</tex>.#: Иначе либо <tex>k < l</tex> и <tex>x[k] \ne y[l + k]</tex>, либо <tex>k = l</tex>. Если <tex>k = l</tex>, то вхождение <tex>x </tex> в <tex>y </tex> найдено. В обоих случаях следующая тройка вычисляется , как в случае <tex>l < i < m </tex>.  [[Файл:Apostolico-Crochemore-Example.png]] ==Псевдокод== '''void''' getT('''string''' x, '''int''' t[]): <font color=green>//функция, вычисляющая массив <tex>t</tex> для строки <tex>x</tex></font> '''int''' i = 0 '''int''' j = t[0] = -1 '''while''' i < x.size '''while''' j > -1 '''and''' x[i] <tex>\neq</tex> x[j] j = t[j] i++ j++ '''if''' i < m '''and''' x[i] == x[j] t[i] = t[j] '''else''' t[i] = j '''vector''' aG('''string''' x, '''string''' y): <font color=green>//<tex>x</tex> {{---}} образец, <tex>y</tex> {{---}} текст</font> '''int''' l '''int''' t[x.size + 1] '''vector''' v <font color=green>//этап предпосчета</font> getT(x, t) <font color=green>//вычисление значения <tex>l</tex> </font> '''for''' l = 1; x[l - 1] == x[l]; l++ '''if''' l == x.size l = 0 <font color=green>//этап поиска</font> '''int''' i = l '''int''' j = 0 '''int''' k = 0 '''while''' j <tex>\leqslant</tex> y.size - x.size '''while''' i < x.size '''and''' x[i] == y[i + j] <font color=green>// если <tex>x[i] = y[i + j]</tex></font> ++i <font color=green>// тогда следующая тройка <tex>(i + 1, j, k)</tex></font> '''if''' i <tex>\geqslant</tex> x.size '''while''' k < l '''and''' x[k] == y[j + k] <font color=green>// если <tex>k < l</tex> и <tex>x[k] = y[j + k]</tex></font> ++k <font color=green>// тогда следующая тройка <tex>(i, j, k + 1)</tex></font> '''if''' k <tex>\geqslant</tex> l <font color=green>// если <tex>k = l</tex></font> v.pushBack(j) <font color=green>// тогда найдена подстрока в позиции j</font> j += i - t[i] <font color=green>// вычисляем новый сдвиг</font> '''if''' i == l k = max(0, k - 1) <font color=green>// если <tex>i = l</tex> и <tex>x[i] \neq y[i + j]</tex>, тогда следующая тройка <tex>(l, j + 1, \max(0, k - 1))</tex></font> '''else if''' t[i] <tex>\leqslant</tex> l <font color=green>// если <tex>t[i] \leqslant l</tex>, тогда следующая тройка <tex>(l, i + j - t[i], \max(0, t[i]))</tex></font> k = max(0, t[i]) i = l '''else''' <font color=green>// если <tex>t[i] > l</tex>, тогда следующая тройка <tex>(t[i], i + j - t[i], l)</tex></font> k = l i = t[i] '''return''' v ==Пример=={| class = "wikitable"! Изображение !! <tex>(i, j, k)</tex> !! Описание|-align="center"|[[Файл:Apostolico-Crochemore-step-1.png|500px]]|<tex>(1, 0, 0)</tex>|Подставив шаблон к позиции <tex>0</tex> получим, что <tex>x[1] \neq y[1]</tex>. Вычислив сдвиг, получим <tex>j = 1</tex>.|-align="center"|[[Файл:Apostolico-Crochemore-step-2.png|500px]]|<tex>(1, 1, 0)</tex>|Подставив шаблон к позиции <tex>1</tex> получим, что <tex>x[0, \ldots , 3] = y[1, \ldots , 4]</tex>. Следовательно, <tex>x</tex> подстрока <tex>y</tex> в позиции <tex>1</tex>. Вычислив сдвиг, получим <tex>j = 4</tex>.|-align="center"|[[Файл:Apostolico-Crochemore-step-3.png|500px]]|<tex>(1, 4, 1)</tex>|Подставив шаблон к позиции <tex>4</tex> получим, что <tex>x[1] \neq y[5]</tex>. Вычислив сдвиг, получим <tex>j = 5</tex>.|-align="center"|[[Файл:Apostolico-Crochemore-step-4.png|500px]]|<tex>(1, 5, 0)</tex>|Подставив шаблон к позиции <tex>5</tex> получим, что <tex>x[1] \neq y[6]</tex>. Вычислив сдвиг, получим <tex>j = 6</tex>.|-align="center"|[[Файл:Apostolico-Crochemore-step-5.png|500px]]|<tex>(1, 6, 0)</tex>|Подставив шаблон к позиции <tex>6</tex> получим, что <tex>x[1] \neq y[7]</tex>. Вычислив сдвиг, получим <tex>j = 7</tex>.|-align="center"|[[Файл:Apostolico-Crochemore-step-6.png|500px]]|<tex>(1, 7, 0)</tex>|Подставив шаблон к позиции <tex>7</tex> получим, что <tex>x[1] \neq y[8]</tex>. Вычислив сдвиг, получим <tex>j = 8</tex>.|-align="center"|[[Файл:Apostolico-Crochemore-step-7.png|500px]]|<tex>(1, 8, 0)</tex>|Подставив шаблон к позиции <tex>8</tex> получим, что <tex>x[0, \ldots , 3] = y[8, \ldots , 11]</tex>. Следовательно, <tex>x</tex> подстрока <tex>y</tex> в позиции <tex>8</tex>.|-|}

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

*[[wikipedia:en:Apostolico–Giancarlo algorithm | Wikipedia {{---}} Apostolico–Giancarlo algorithm]]*[http://www-igm.univ-mlv.fr/~lecroq/string/node12.html#SECTION00120 Краткое описание алгоритма, пример работыwww-igm.univ-mlv.fr — Apostolico-Crochemore algorithm]