Алгоритм Ахо — Корасик

Алгоритм Ахо — Корасик

Алгоритм Ахо — Корасик

Алгоритм Ахо — Корасик — алгоритм поиска подстроки, созданный Альфредом Ахо и Маргарет Корасик. Алгоритм реализует поиск множества подстрок из словаря в данной строке. Время работы пропорционально O(M + N + K), где N — длина строки-образца, M — суммарная длина строк словаря, а K — длина ответа, то есть суммарная длина вхождений слов из словаря в строку-образец. Поэтому суммарное время работы может быть квадратичным (например, если в строке «ааааааа» мы ищем слова «а», «аа», «ааа», …).

Принцип работы

Алгоритм строит конечный автомат, которому затем передаёт строку поиска. Автомат получает по очереди все символы строки и переходит по соответствующим рёбрам. Если автомат пришёл в конечное положение, соответствующая строка словаря присутствует в строке поиска.

Внешние ссылки



Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Полезное


Смотреть что такое "Алгоритм Ахо — Корасик" в других словарях:

  • Алгоритм Ахо — Алгоритм Ахо  Корасик  алгоритм поиска подстроки, созданный Альфредом Ахо и Маргарет Корасик. Алгоритм реализует поиск множества подстрок из словаря в данной строке. Время работы пропорционально , где   длина строки образца,   …   Википедия

  • Алгоритм Ахо-Корасик — …   Википедия

  • Алгоритм Кнута — Морриса — Пратта — (КМП алгоритм) алгоритм поиска образца (подстроки) в строке. Алгоритм был открыт Д. Кнутом и В. Праттом и, независимо от них, Д. Моррисом[1]. Результаты своей работы они опубликовали совместно в 1977 году.[2] Содержание 1 Постановка задачи …   Википедия

  • Алгоритм Кнута — Алгоритм Кнута  Морриса  Пратта (КМП алгоритм)  алгоритм, осуществляющий поиск подстроки в строке. Алгоритм был открыт Д. Кнутом и В. Праттом и, независимо от них, Д. Моррисом[1]. Результаты своей работы они опубликовали совместно… …   Википедия

  • Ахо, Альфред — В Википедии есть статьи о других людях с такой фамилией, см. Ахо. Альфред Ахо Alfred Vaino Aho Дата рождения: 9 августа 1941(1941 08 09) (71 год) Место рождения: Тимминс …   Википедия

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

  • КМП-алгоритм — Алгоритм Кнута Морриса Пратта (КМП алгоритм) алгоритм поиска образца (подстроки) в строке. Содержание 1 Постановка задачи 2 История возникновения …   Википедия

  • Поиск подстроки — Поиск информации  одно из основных использований компьютера. Одна из простейших задач поиска информации  поиск точно заданной подстроки в строке. Тем не менее, эта задача чрезвычайно важна  она применяется в текстовых редакторах,… …   Википедия

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Программируемые алгоритмы —       Служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавл …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»