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