251
правка
Изменения
→Пример работы
==Пример работы==
Пусть нам дана строка <tex>y = GCATCGCAGAGAGTATACAGTACG</tex> и образец <tex>x=GCAGAGAG</tex>
Построим массив <tex>bmBc</tex>:
[[Файл:RaitaPre.png|250px]]
Рассмотрим шаги алгоритма:
{| class = "wikitable"
! Изображение !! <tex>(j, bmBc[y[j]])</tex> !! Описание
|-align="center"
|[[Файл:Raita1.png|550px]]
|<tex>(7, 1)</tex>
|Делаем сравнение последних символов, оно неудачно, сдвигаемся на <tex>bmGs[7] = bmBc[A]-8+8 = 1</tex>.
|-align="center"
|[[Файл:Tbme2.PNG|550px]]
|<tex>(8, 2)</tex>
|Последние два символа совпали, сдвигаемся на <tex>bmGs[5] = bmBc[C] - 8 + 6 = 4</tex>.
|-align="center"
|[[Файл:Tbme3.PNG|550px]]
|<tex>(12, 2)</tex>
|Все символы совпали, Продолжим работу (для примера, в обычном варианте на этом этапе мы можем выйти, если требуется найти только одно вхождение) и сдвинемся на <tex>bmGs[0] = 7</tex>.
|-align="center"
|[[Файл:Tbme4.PNG|550px]]
|<tex>(19, 2)</tex>
|Последние два символа совпали, сдвигаемся на <tex>bmGs[5] = bmBc[C] - 8 + 6 = 4</tex>
|-align="center"
|[[Файл:Tbme5.PNG|550px]]
|<tex>(23, 1)</tex>
|Последние символы совпали, сравниваем предпоследние, сдвигаемся. Строка закончилась, выходим.
|-
|}
В итоге, чтобы найти одно вхождение образца длиной <tex>m = 8</tex> в образце длиной <tex>n = 24</tex> нам понадобилось <tex>15</tex> сравнений символов
==См. также==
