Изменения
→Пример реализации
== Пример реализации ==
Ниже представлена реализация некоторых функций (используется ленивая рекурсия).<br />
<tex>k</tex> {{---}} это размер алфавита.
'''Структура вершины:'''
'''vector<int>''' leafPatternNumber <font color=green>// номера строк, за которые отвечает терминал</font>
'''Функция, для вычисления суффиксной ссылки:'''
'''Node''' getSuffLink('''Node''' v):
'''if''' v.suffLink == ''null'' <font color=green>// если суффиксная ссылка ещё не вычислена</font>
'''return''' v.suffLink
'''Функция, для вычисления перехода:'''
'''Node''' getLink('''Node''' v, '''char''' c):
'''if''' v.go[c] == ''null'' <font color=green>// если переход по символу c ещё не вычислен</font>
'''return''' v.go[c]
'''Функция, для вычисления сжатой суффиксной ссылки:'''
'''Node''' getUp('''Node''' v):
'''if''' v.up == ''null'' <font color=green>// если сжатая суффиксная ссылка ещё не вычислена</font>
'''return''' v.up
'''Функция, для добавление добавления строки в бор:'''
'''fun''' addString('''string''' s, '''int''' patternNumber):
'''Node''' cur = root
cur.isLeaf = ''true''
cur.leafPatternNumber.pushBack(patternNumber)
'''Функция, для процессинга текста (поиск, встречается строка или нет):'''
'''fun''' processText('''string''' t):
'''Node''' cur = root
== Оптимизации ==
Существует несколько оптимизаций данного алгоритма, направленных на случаи, когда нас интересует только первое вхождение образца в текст: # '''Сброс сжатых суффиксных ссылок для посещённых вершин. Если требуется найти только первое вхождение строки в текст, то существенно ''' #: Существенно ускорить работу алгоритма могут пометки о посещённости узла, т.е. то есть если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.# '''Сброс пометки терминальной вершины. ''' #: В изначальном множестве образцов могут быть дублирующиеся строки. Если же таких строк будет многоМы можем хотеть из различать, то наш алгоритм будет очень долго работатьесли с одинаковыми строками связана разная мета-информация. Если же мы будем делать Тогда при попадании в терминальную вершину можно осуществлять сброс пометки этой терминальной вершины, когда обнаруживаем ее что сэкономит время на обновлении информации о вхождении образцов в первый разтекст. Тривиальным примером, то таким образом ускорим время работыв котором возникает ситуация долгой обработки, так как нас будет интересовать служит огромное множество образцов из одинаковых символов и текст только первое вхождениеиз этих символов.
== Поиск шаблонов с масками ==
