'

Информатика Курсовая работа

Понравилась презентация – покажи это...





Слайд 0

Информатика Курсовая работа МИЭМ, 25.12.2009 Изучить алгоритм быстрого поиска Бойера-Мура (БМ) и реализовать его с визуализацией. Выполнил: Матвеев А.В.


Слайд 1

Задачи: МИЭМ, 25.12.2009 Описание алгоритма Реализация Варианты


Слайд 2

3 Описание алгоритма Алгоритм Бойера — Мура поиска строки считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером (англ. Robert S. Boyer) и Джеем Муром (англ. J Strother Moore) в 1977 году. Преимущество этого алгоритма в том, что ценой некоторого количества предварительных вычислений над шаблоном (но не над строкой, в которой ведётся поиск) шаблон сравнивается с исходным текстом не во всех позициях — часть проверок пропускаются как заведомо не дающие результата.


Слайд 3

Строится таблица смещений для первого символов шаблона. Совмещается начало строки и шаблона, проверка начинается с начала шаблона. Если символ шаблона и соответствующий ему при наложении символ строки не совпадают. Производится сдвиг и снова начинается проверка с последнего символа. Весь алгоритм выполняется до тех пор, пока либо не будет найдено вхождение искомого образца, либо не будет достигнут конец строки. Описание алгоритма 4


Слайд 4

5 Реализация упрощенного алгоритма Для шаблона строится таблица совпадений первого символа строка шаблон Накладываем образец на строку


Слайд 5

6 Реализация упрощенного алгоритма


Слайд 6

7 Варианты


×

HTML:





Ссылка: