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