177
правок
Изменения
Нет описания правки
--j
i += MAX(bmGs[m - 1 - j], bmBc[y[i]])
==Пример==
Пусть нам дана строка <tex>y = GCATCGCAGAGAGTATACAGTACG</tex> и образец <tex>x=GCAGAGAG</tex>
Построим массивы <tex>bmBc</tex> и <tex>bmGs</tex> :
[[Файл:RaitaPre.png|250px]]
[[Файл:Crochemore.png|300px]]
Рассмотрим шаги алгоритма:
{| class = "wikitable"
! Изображение !! <tex>(j, bmGs[y[j]])</tex> !! Описание
|-align="center"
|[[Файл:BMexample1.png|550px]]
|<tex>(7, 1)</tex>
|Сравниванием последние символы, они неравны, поэтому сдвигаемся.
|-align="center"
|[[Файл:BMexample2.png|550px]]
|<tex>(8, 4)</tex>
|Последние символы совпали. Предпоследние совпали. Третьи символы с конца различны, сдвигаемся.
|-align="center"
|[[Файл:BMexample3.png|550px]]
|<tex>(12, 7)</tex>
|Последние символы совпали, сравниваем далее. Строчка найдена. Продолжаем работу и сдвигаемся.
|-align="center"
|[[Файл:BMexample4.png|550px]]
|<tex>(19, 4)</tex>
|Последние символы совпали. Предпоследние совпали. Третьи символы с конца различны, сдвигаемся.
|-align="center"
|[[Файл:BMexample5.png|550px]]
|<tex>(23, 7)</tex>
|Последние символы совпали, предпоследние различны. Алгоритм закончил работу.
|-align="center"
|}
В итоге, чтобы найти одно вхождение образца длиной <tex>m = 8</tex> в образце длиной <tex>n = 24</tex>, нам понадобилось <tex>18</tex> сравнений символов.
==Асимптотики==
