Изменения
→Пример реализации
'''Структура вершины:'''
'''struct''' Node:
'''Node''' son[k] <font color=green>// массив сыновей; k {{---}} это размер алфавита</font> '''Node''' go[k] <font color=green>// массив переходов (запоминаем переходы в ленивой рекурсии)</font> '''Node''' parent <font color=green>// вершина родитель</font> '''Node''' suffLink <font color=green>// суффиксная ссылка (вычисляем в ленивой рекурсии)</font> '''Node''' up <font color=green>// сжатая суффиксная ссылка</font> '''char''' charToParent <font color=green>// символ, ведущий к родителю</font> '''bool''' isLeaf <font color=green>// флаг, является ли вершина терминалом</font> '''vector<int>''' leafPatternNumber <font color=green>// номера строк, за которые отвечает терминал</font>
'''Функция, для вычисления суффиксной ссылки:'''
'''Node''' getSuffLink('''Node''' v):
'''if''' '''not''' v.suffLink <font color=green>// если суффиксная ссылка ещё не вычислена</font>
'''if''' v == root '''or''' v.parent == root
v.suffLink = root
'''Функция, для вычисления перехода:'''
'''Node''' getLink('''Node''' v, '''char''' c):
'''if''' '''not''' v.go[c] <font color=green>// если переход по символу c ещё не вычислен</font>
'''if''' v.son[c]
v.go[c] = v.son[c]
'''Функция, для вычисления сжатой суффиксной ссылки:'''
'''Node''' getUp('''Node''' v):
'''if''' '''not''' v.up <font color=green>// если сжатая суффиксная ссылка ещё не вычислена</font>
'''if''' getSuffLink(v).isLeaf
v.up = getSuffLink(v)
'''Функция, для процессинга текста (поиск, встречается строка или нет):'''
'''fun''' processText('''string const&''' t, '''vector<bool>&''' found): <font color=green>// found - это вектор, длина которого равна количеству строк</font>
found.assign(w, ''false'') <font color=green>// w - количество строк</font>
'''Node''' cur = root
'''for''' i = 0 '''to''' t.length - 1
