Изменения
→Пример реализации
'''Структура вершины:'''
'''struct''' Node:
'''Node*''' son[SZ] <font color=green>// массив сыновей; SZ - это размер алфавита</font> '''Node*''' go[SZ] <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>
'''Функция, для вычисления суффиксной ссылки:'''
'''Node*''' getSuffLink('''Node*''' v): '''if''' '''not'''(v->.suffLink) <font color=green>// если суффиксная ссылка ещё не вычислена</font> '''if''' v == root '''or''' v->.parent == root v->.suffLink = root
'''else'''
v->.suffLink = getGo(getSuffLink(v->.parent), v->.charToParent) '''return''' v->.suffLink
'''Функция, для вычисления перехода:'''
'''Node*''' getGo('''Node*''' v, '''char''' c): '''if''' '''not'''(v->.go[c]) <font color=green>// если переход по символу c ещё не вычислен</font> '''if''' v->.son[c] v->.go[c] = v->.son[c]
'''else''' '''if''' v == root
v->.go[c] = root
'''else'''
v->.go[c] = getGo(getSuffLink(v), c) '''return''' v->.go[c]
'''Функция, для вычисления сжатой суффиксной ссылки:'''
'''Node*''' getUp('''Node*''' v): '''if''' '''not'''(v->.up) <font color=green>// если сжатая суффиксная ссылка ещё не вычислена</font> '''if''' getSuffLink(v)->.isLeaf v->.up = getSuffLink(v)
'''else''' '''if''' getSuffLink(v) == root
v->.up = root
'''else'''
v->.up = getUp(getSuffLink(v)) '''return''' v->.up
'''Функция, для добавление строки в бор:'''
'''fun''' addString('''string const&''' s, '''int''' patternNumber):
'''Node*''' cur = root
'''for''' i = 0 '''to''' s.length - 1
'''char''' c = s[i] - 'a'
'''if''' cur->.son[c] == 0 cur->.son[c] = Node
<font color=green>/* здесь также нужно обнулить указатели на переходы и сыновей */</font>
cur->.son[c]->.suffLink = 0 cur->.son[c]->.up = 0 cur->.son[c]->.parent = cur cur->.son[c]->.charToParent = c cur->.son[c]->.isLeaf = ''false'' cur = cur->.son[c] cur->.isLeaf = ''true'' cur->.leafPatternNumber.push_back(patternNumber)
'''Функция, для процессинга текста (поиск, встречается строка или нет):'''
'''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
'''char''' c = t[i] - 'a'
cur = getGo(cur, c)
'''for''' j = 0 '''to''' cur->.leafPatternNumber.size - 1 found[cur->.leafPatternNumber[j]] = ''true''
<font color=green>/* В этом месте кода должен выполняться переход по '''сжатой''' суффиксной ссылке getUp(cur). Для вершины,
обнаруженной по ней тоже ставим, что она найдена, затем повторяем для её сжатой суффиксной ссылки
