Выполнил: Матвеев А.В.
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
ИнформатикаКурсовая работа презентация
Содержание
- 1. ИнформатикаКурсовая работа
- 2. Задачи: МИЭМ, 25.12.2009 Описание алгоритма Реализация Варианты
- 3. Описание алгоритма Алгоритм Бойера — Мура поиска строки
- 4. Строится таблица смещений для первого символов шаблона.
- 5. Реализация упрощенного алгоритма Для шаблона строится таблица
- 6. Реализация упрощенного алгоритма
- 7. Варианты
Задачи: МИЭМ, 25.12.2009 Описание алгоритма Реализация Варианты
Слайд 1Информатика
Курсовая работа
МИЭМ, 25.12.2009
Изучить алгоритм быстрого поиска Бойера-Мура (БМ) и реализовать его
с визуализацией.
Слайд 3Описание алгоритма
Алгоритм Бойера — Мура поиска строки считается наиболее быстрым среди алгоритмов
общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером (англ. Robert S. Boyer) и Джеем Муром (англ. J Strother Moore) в 1977 году.
Преимущество этого алгоритма в том, что ценой некоторого количества предварительных вычислений над шаблоном (но не над строкой, в которой ведётся поиск) шаблон сравнивается с исходным текстом не во всех позициях — часть проверок пропускаются как заведомо не дающие результата.
Преимущество этого алгоритма в том, что ценой некоторого количества предварительных вычислений над шаблоном (но не над строкой, в которой ведётся поиск) шаблон сравнивается с исходным текстом не во всех позициях — часть проверок пропускаются как заведомо не дающие результата.
Слайд 4Строится таблица смещений для первого символов шаблона.
Совмещается начало строки и шаблона,
проверка начинается с начала шаблона.
Если символ шаблона и соответствующий ему при наложении символ строки не совпадают. Производится сдвиг и снова начинается проверка с последнего символа.
Весь алгоритм выполняется до тех пор, пока либо не будет найдено вхождение искомого образца, либо не будет достигнут конец строки.
Если символ шаблона и соответствующий ему при наложении символ строки не совпадают. Производится сдвиг и снова начинается проверка с последнего символа.
Весь алгоритм выполняется до тех пор, пока либо не будет найдено вхождение искомого образца, либо не будет достигнут конец строки.
Описание алгоритма
Слайд 5Реализация упрощенного алгоритма
Для шаблона строится таблица совпадений первого символа
строка
шаблон
Накладываем образец на
строку
