141
правка
Изменения
→Пример реализации: (продолжение)
== Пример реализации ==
Ниже представлена реализация на C++ некоторых функций (используется ленивая рекурсия).<br /><br />
'''Структура вершины:'''
struct Node {
Node* son[26]; <font color=green>// массив сыновей</font> Node* go[26]; <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> std::vector<int> leafPatternNumber; <font color=green>// номера образцов, за которые отвечает терминал</font>
};
'''Функция, для вычисления суффиксной ссылки:'''
Node* getSuffLink(Node* v) {
if (!v->suffLink) { <font color=green>// если суффиксная ссылка ещё не вычислена</font>
if (v == root || v->parent == root) {
v->suffLink = root;
}
return v->suffLink;
}
'''Функция, для вычисления перехода:'''
Node* getGo(Node* v, char c) {
if (!v->go[c]) { <font color=green>// если переход по символу c ещё не вычислен</font>
if (v->son[c]) {
v->go[c] = v->son[c];
} else {
v->go[c] = (v == root) ? root : getGo(getSuffLink(v), c);
}
}
return v->go[c];
}
'''Функция, для вычисления сжатой суффиксной ссылки:'''
Node* getUp(Node* v) {
if (!v->up) { <font color=green>// если сжатая суффиксная ссылка ещё не вычислена</font>
if (getSuffLink(v)->leaf) {
v->up = getSuffLink(v);
} else if (getSuffLink(v) == root) {
v->up = 0;
} else {
v->up = getUp(getSuffLink(v));
}
}
return v->up;
}
