Ответ
ACT-дерево (Aho-Corasick Trie) — это структура данных для эффективного поиска множества подстрок в тексте. Основано на алгоритме Ахо-Корасик, который объединяет префиксное дерево (trie) с автоматом для быстрого перехода между состояниями.
Ключевые особенности:
- Строится на основе набора шаблонов (строк для поиска)
- Позволяет искать все шаблоны за O(n + m + k), где n — длина текста, m — сумма длин шаблонов, k — число вхождений
- Использует три типа ссылок: переходы по символам, суффиксные ссылки и выходные ссылки
Пример использования в Go:
import "github.com/cloudflare/ahocorasick"
func main() {
patterns := []string{"he", "she", "his", "hers"}
matcher := ahocorasick.NewMatcher(patterns)
text := "ushers"
matches := matcher.Match([]byte(text))
// matches содержит позиции всех найденных паттернов
}Применяется в антивирусах, поисковых системах, анализе текста.
