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