Алгоритм Апостолико-Крочемора — различия между версиями
(→Псевдокод) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 4 промежуточные версии 3 участников) | |||
Строка 21: | Строка 21: | ||
− | Пусть теперь <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>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>i</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>(i, j, k)</tex> где: | Во время поиска вхождений мы рассматриваем данную тройку <tex>(i, j, k)</tex> где: | ||
Строка 57: | Строка 58: | ||
i++ | i++ | ||
j++ | j++ | ||
− | '''if''' x[i] == x[j] | + | '''if''' i < m '''and''' x[i] == x[j] |
t[i] = t[j] | t[i] = t[j] | ||
'''else''' | '''else''' | ||
Строка 64: | Строка 65: | ||
'''vector''' aG('''string''' x, '''string''' y): <font color=green>//<tex>x</tex> {{---}} образец, <tex>y</tex> {{---}} текст</font> | '''vector''' aG('''string''' x, '''string''' y): <font color=green>//<tex>x</tex> {{---}} образец, <tex>y</tex> {{---}} текст</font> | ||
'''int''' l | '''int''' l | ||
− | '''int''' t[x.size] | + | '''int''' t[x.size + 1] |
'''vector''' v | '''vector''' v | ||
Строка 89: | Строка 90: | ||
'''if''' i == l | '''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> | 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 | + | '''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 | '''return''' v | ||
Строка 104: | Строка 104: | ||
|[[Файл:Apostolico-Crochemore-step-1.png|500px]] | |[[Файл:Apostolico-Crochemore-step-1.png|500px]] | ||
|<tex>(1, 0, 0)</tex> | |<tex>(1, 0, 0)</tex> | ||
− | | | + | |Подставив шаблон к позиции <tex>0</tex> получим, что <tex>x[1] \neq y[1]</tex>. Вычислив сдвиг, получим <tex>j = 1</tex>. |
|-align="center" | |-align="center" | ||
|[[Файл:Apostolico-Crochemore-step-2.png|500px]] | |[[Файл:Apostolico-Crochemore-step-2.png|500px]] | ||
|<tex>(1, 1, 0)</tex> | |<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" | |-align="center" | ||
|[[Файл:Apostolico-Crochemore-step-3.png|500px]] | |[[Файл:Apostolico-Crochemore-step-3.png|500px]] | ||
|<tex>(1, 4, 1)</tex> | |<tex>(1, 4, 1)</tex> | ||
− | | | + | |Подставив шаблон к позиции <tex>4</tex> получим, что <tex>x[1] \neq y[5]</tex>. Вычислив сдвиг, получим <tex>j = 5</tex>. |
|-align="center" | |-align="center" | ||
|[[Файл:Apostolico-Crochemore-step-4.png|500px]] | |[[Файл:Apostolico-Crochemore-step-4.png|500px]] | ||
|<tex>(1, 5, 0)</tex> | |<tex>(1, 5, 0)</tex> | ||
− | | | + | |Подставив шаблон к позиции <tex>5</tex> получим, что <tex>x[1] \neq y[6]</tex>. Вычислив сдвиг, получим <tex>j = 6</tex>. |
|-align="center" | |-align="center" | ||
|[[Файл:Apostolico-Crochemore-step-5.png|500px]] | |[[Файл:Apostolico-Crochemore-step-5.png|500px]] | ||
|<tex>(1, 6, 0)</tex> | |<tex>(1, 6, 0)</tex> | ||
− | | | + | |Подставив шаблон к позиции <tex>6</tex> получим, что <tex>x[1] \neq y[7]</tex>. Вычислив сдвиг, получим <tex>j = 7</tex>. |
|-align="center" | |-align="center" | ||
|[[Файл:Apostolico-Crochemore-step-6.png|500px]] | |[[Файл:Apostolico-Crochemore-step-6.png|500px]] | ||
|<tex>(1, 7, 0)</tex> | |<tex>(1, 7, 0)</tex> | ||
− | | | + | |Подставив шаблон к позиции <tex>7</tex> получим, что <tex>x[1] \neq y[8]</tex>. Вычислив сдвиг, получим <tex>j = 8</tex>. |
|-align="center" | |-align="center" | ||
|[[Файл:Apostolico-Crochemore-step-7.png|500px]] | |[[Файл:Apostolico-Crochemore-step-7.png|500px]] | ||
|<tex>(1, 8, 0)</tex> | |<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>. |
|- | |- | ||
|} | |} |
Текущая версия на 19:15, 4 сентября 2022
Алгоритм Апостолико — Крочемора (англ. Apostolico — Crochemore algorithm) — алгоритм поиска подстроки в строке.
Описание алгоритма
Нам даны:
— текст, — образец, , .Для начала рассмотрим ситуацию, когда мы сравниваем наш образец с
. Предположим, что при . Тогда и . Когда сдвиг возможен, разумно ожидать, что префикс шаблона совпадет c некоторым суффиксом . Более того, если мы хотим избежать несовпадения при сдвиге, то нужно, чтобы символ, следующий за префиксом в шаблоне, не совпадал с . Такой наибольший префикс называется помеченным бордером строки .
Определение: |
Помеченный бордер (англ. tagged border) строки | — строка .
Введем обозначение: пусть — длина наибольшего бордера для за которым следует символ и если нет такого помеченного бордера, где ( ). Затем, после сдвига, сравнение можно продолжить между символами и не потеряв никакого вхождения в и избежав отступа по тексту (смотри рисунок ниже).
Примечание:
— помеченный бордер строки .
Пусть теперь , если и , иначе равно позиции первого элемента, который не равен ( , где , , , ). При каждой подстановке шаблона к тексту к позиции мы проводим следующие сравнения: .
Во время поиска вхождений мы рассматриваем данную тройку где:
- шаблон сравнивается с
- и
- и
(см. рисунок ниже)
Вначале инициализируем эту тройку
. Теперь опишем, как по уже вычисленной тройке перейти к следующей. Возможны три случая в зависимости от значения :-
- Если , тогда следующая тройка .
- Если , тогда следующая тройка .
:
-
- Если , тогда следующая тройка .
- Если
- Если , тогда следующая тройка .
- Если , тогда следующая тройка .
, тогда возможны два случая в зависимости от значения :
-
- Если и , тогда следующая тройка .
- Иначе либо и , либо . Если , то вхождение в найдено. В обоих случаях следующая тройка вычисляется, как в случае .
:
Псевдокод
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 i < m and x[i] == x[j] t[i] = t[j] else t[i] = j vector aG(string x, string y): // — образец, — текст int l int t[x.size + 1] vector v //этап предпосчета getT(x, t) //вычисление значения for l = 1; x[l - 1] == x[l]; l++ if l == x.size l = 0 //этап поиска 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 // если v.pushBack(j) // тогда найдена подстрока в позиции 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] return v
Пример
Асимптотика алгоритма
Этап предподсчета, а именно вычисление массива
и переменной занимает времени и константное количество памяти. Этап поиска занимает времени, более того, алгоритм в худшем случае выполнит сравнений.