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

Материал из Википедии — свободной энциклопедии

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

[править] Принцип работы

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