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

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

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

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

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

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

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

7 7 Варианты Название Предварительная обработка Сложность Сред.Макс. Алгоритм Бойера-Мура- Хорспула O(n+σ)