Каталог статей - CHASOLIMP & РОМАШКА

Часть 1. Поиск подстроки в строке. Простейший алгоритм

Простейший (медленный) алгоритм или метод "грубой силы"

Часть 2. Поиск подстроки в строке. Алгоритм Бойера-Мура

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

Часть 3. Поиск подстроки в строке. Более эффективный вариант

Рассмотренный упрощенный алгоритм вполне пригоден с практической точки зрения (и часто применяется). Нельзя не заметить, что результаты сравнений используются недостаточно эффективно. Действительно, на втором шаге, когда у нас совпали три символа, мы, зная, что последовательность “bad” встречается в образце только один раз, могли бы сразу сместить образец на всю его длину, а не на один символ.

Часть 4. Поиск подстроки в строке. Алгоритм Рабина-Карпа

Алгоритм Рабина-Карпа - это алгоритм поиска строки, который ищет шаблон, то есть подстроку, в тексте используя хеширование. Он был разработан в 1987 году Майклом Рабином и Ричардом Карпом. Он не широко используется для поиска одиночного шаблона, но имеет значительную теоретическую важность и очень эффективен в поиске совпадений множественных шаблонов

Часть 5. Алгоритмы Морриса-Пратта и Кнута-Морриса-Пратта

Исследователи хотели найти способы более полно использовать информацию, полученную во время сканирования (алгоритм грубой силы ее "выбрасывает"). Оказывается, размер сдвига образца можно увеличить, одновремеменно запомнив части текста, совпадающие с образцом. Это позволит нам избежать ненужных сравнений и, тем самым, резко увеличить скорость поиска.