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