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

Матеріал з Вікіпедії — вільної енциклопедії.
(Перенаправлено з Алгоритм Ахо-Корасік)
Перейти до: навігація, пошук

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

Принцип роботи[ред.ред. код]

Алгоритм будує скінченний автомат, якому потім передає рядок пошуку. Автомат отримує по черзі всі символи рядка й переходить за відповідними ребрами. Якщо автомат досяг кінцевого стану, відповідний рядок словника присутній в рядку пошуку.

Література[ред.ред. код]

Див. також[ред.ред. код]

Посилання[ред.ред. код]

Візуалізатор алгоритму Ахо — Корасіка
Реалізація алгоритму на C#
Реалізація алгоритму на Java
Реалізація алгоритму на Erlsnd
Детальніший опис алгоритму