Поиск подстрок
Определения
Определения
Постановка задачи
Пример
Простой алгоритм
Применение простого алгоритма
Алгоритм Рабина-Карпа
Использование хеш-функции
Хеш функция
Алгоритм Рабина-Карпа
Алгоритм Рабина-Карпа
Алгоритм Рабина-Карпа
Алгоритм Рабина-Карпа
Алгоритм Рабина-Карпа(продолжение)
Временная сложность алгоритма Рабина-Карпа
Поиск подстрок с помощью конечных автоматов(abcd)
Конечные автоматы
Алгоритм
Фрагмент алгоритма1
Фрагмент алгоритма2
Фрагмент алгоритма3
Фрагмент алгоритма4
Усовершенствованный алгоритм
Алгоритм Кнута - Морриса – Пратта (КМП)
КМП
π-функция
π-функция
Пример
Пример
Пример реализации
Алгоритм КМП-поиска
Алгоритм КМП
Z- функция
Алгоритм поиска строки Бойера —Мура
Описание алгоритма.
Сканирование слева направо, сравнение справа налево. 
Сканирование слева направо, сравнение справа налево
Эвристика стоп-символа. 
Эвристика стоп-символа. 
Эвристика стоп-символа. 
Эвристика совпавшего суффикса
Алгоритм Бойера —Мура
Таблица стоп-символов
Таблица стоп-символов
Таблица суффиксов
Таблица суффиксов
Таблица суффиксов
Быстрый алгоритм вычисления таблицы суффиксов
Быстрый алгоритм вычисления таблицы суффиксов
Пример работы алгоритма БМ
Пример работы алгоритма БМ
Пример работы алгоритма БМ
Пример работы алгоритма БМ
Алгоритм Бойера-Мура
Алгоритм Бойера-Мура
Алгоритм Бойера-Мура
281.00K
Category: programmingprogramming

Поиск подстрок

1. Поиск подстрок

2. Определения

• Алфавит – конечное множество символов.
• Строка (слово) – это последовательность
символов из некоторого алфавита. Длина
строки – количество символов в строке.
• X=x[1]x[2]...x[n] – строка длинной n, где x[i]
– i-ый символ строки Х, принадлежащий
алфавиту.
• Строка, не содержащая ни одного символа,
называется пустой.

3. Определения

• Строка X называется подстрокой строки Y,
если найдутся такие строки Z1 и Z2, что
Y=Z1XZ2.
• Подстрока X называется префиксом строки
Y, если есть такая подстрока Z, что Y=XZ.
• Подстрока X называется суффиксом строки
Y, если есть такая подстрока Z, что Y=ZX.

4. Постановка задачи

• Есть образец и строка, надо определить
индекс, начиная с которого
образец содержится в строке. Если не
содержится — вернуть индекс, который не
может быть интерпретирован как позиция в
строке (например, отрицательное число).
• При необходимости отслеживать каждое
вхождение образца в текст имеет смысл
завести дополнительную функцию,
вызываемую при каждом обнаружении
образца.

5. Пример

• Дана последовательность символов
x[1]..x[n]. Определить, встречаются ли в ней
идущие друг за другом символы "abcd".
(Другими словами, требуется выяснить,
есть ли в слове x[1]..x[n]
подслово "abcd".)

6. Простой алгоритм

• Решение. Имеется примерно n (если быть точным, n-3)
позиций, на которых может находиться искомая подстрока
в исходной строке.
Для каждой из позиций можно проверить, действительно
ли с нее начинается подстрока , сравнив четыре символа.
Но обычно слово x[1]..x[n] просматривается слева
направо, до появления буквы 'a'. Как только она
появилась, ищем за ней букву 'b', затем 'c', и, наконец, 'd'.
Если ожидания оправдываются, то слово "abcd"
обнаружено. Если же какая-то из нужных букв не
появляется, начинаем поиск с новой позиции.

7. Применение простого алгоритма

8. Алгоритм Рабина-Карпа

Пусть алфавит D={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, то
есть каждый символ в алфавите есть d–
ичная цифра, где d=│D│.
Пример
Образец имеет вид W = 3 1 4 1 5
Вычисляем значения чисел из окна длины
|W|=5 по mod q, q — простое число.

9. Использование хеш-функции

23590(mod 13)=8, 35902(mod 13)=9, 59023(mod
13)=9, …
k1=31415 (mod 13) 7– вхождение образца,
k2=67399(mod 13) 7– холостое срабатывание.

10. Хеш функция

Hash(p[1..m] =
English     Русский Rules