Изменения
→Оптимизации
Существует несколько оптимизаций данного алгоритма:
# Сброс сжатых суффиксных ссылок для посещённых вершин. Если требуется найти только первое вхождение строки в текст, то существенно ускорить работу алгоритма могут пометки о посещённости узла, т.е. если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.
# Сброс пометки терминальной вершины. В изначальном множестве образцов могут быть дублирующиеся строки. Если же таких строк будет много, то наш алгоритм будет очень долго работать. Если же мы будем делать сброс пометки терминальной вершины, когда обнаруживаем ее в первый раз, то таким образом ускорим время работы, так как нас будет интересовать только первое вхождение.
== Поиск шаблонов с масками ==
