Изменения

Перейти к: навигация, поиск

Алгоритм Райта

1009 байт добавлено, 16:20, 27 марта 2016
Пример
[[Файл:RaitaPre.png|thumb|center|Массив <tex>bmBc</tex> после фазы препроцессинга]]
{| class = "wikitable"! Изображение !! <tex>(j, bmBc[y[j]])</tex> !! Описание|-align="center"|[[Файл:Raita1.png|thumb|450px|center500px]]|Сдвигаемся на <tex>(7, 1 (bmBc[A])</tex> после сравнения]]|Делаем сравнение последних символов, оно неудачно, сдвигаемся.|-align="center"|[[Файл:Raita2.png|thumb|450px|center500px]]|Сдвигаемся на <tex>(8, 2 (bmBc[G])</tex> после второго сравнения]]|Последние символы совпали, сравниваем первые, сдвигаемся.|-align="center"|[[Файл:Raita3.png|thumb|450px|center500px]]|Сдвигаемся на <tex>(10, 2 (bmBc[G])</tex>]]|Последние символы совпали, сравниваем первые, сдвигаемся.|-align="center"|[[Файл:Raita4.png|thumb|450px|center500px]]|Сдвигаемся на <tex>(12, 2 (bmBc[G])</tex> после всех сравнений]]|Совпали последний, первый и средний символы, пробегаемся по всему шаблону и сравниваем символы. Нашли строчку в тексте. Продолжим работу (для примера, в обычном варианте на этом этапе мы можем выйти, если требуется найти только одно вхождение) и сдвинемся.|-align="center"|[[Файл:Raita5.png|thumb500px]]|450px|center|Сдвигаемся на <tex>(14, 1 (bmBc[A])</tex>]]|Делаем сравнение последних символов, оно неудачно, сдвигаемся.|-align="center"|[[Файл:Raita6.png|thumb|450px500px]]|center|Сдвигаемся на <tex>(15, 8 (bmBc[T])</tex>]]|Делаем сравнение последних символов, оно неудачно, сдвигаемся.|-align="center"|[[Файл:Raita7.png|thumb|450px|center500px]]|Сдвигаемся на <tex>(23, 2 (bmBc[G])</tex>]]|Последние символы совпали, сравниваем первые, сдвигаемся. Строка закончилась, выхожим.|-|}
В итоге, чтобы найти одно вхождение образца длиной <tex>m = 8</tex> в образце длиной <tex>n = 24</tex> нам понадобилось <tex>18</tex> сравнений символов
317
правок

Навигация