tgoop.com/the_algorithms/4620
Last Update:
Алгоритм Ахо-Корасика
Алгоритм для множественного поиска подстрок в заданном тексте.
Алгоритм:
1. Построение бора (trie) для множества шаблонов (подстрок, которые необходимо найти).
2. Добавление суффиксных ссылок в каждую вершину бора, чтобы обрабатывать несовпадающие префиксы.
3. Присвоение каждой вершине бора "выходных ссылок" в другую вершину с шаблоном, совпадающим с префиксом подстроки из этой вершины.
4. Поиск в тексте: сначала вы начинаете с корневой вершины бора и последовательно проходите по символам текста.
-Если символ не соответствует ни одной исходящей ребру из текущей вершины, вы переходим на суффиксную ссылку и повторяете этот шаг.
-Если символ совпадает с шаблоном в следующей вершине, то удачное совпадение, и вы переходите к следующей вершине.
-Если вы достигли конечной вершины, значит, вы нашли одно из искомых шаблонов.
Сложность: O(n + m + z), где n – длина текста, m – суммарная длина всех шаблонов и z – количество найденных совпадений.
BY Алгоритмы и структуры данных
Share with your friend now:
tgoop.com/the_algorithms/4620