141
правка
Изменения
Пример реализации (ещё не весь)
По очереди просматриваем символы текста. Для очередного символа <tex>c</tex> переходим из текущего состояния <tex>u</tex> в состояние, которое вернёт функция <tex>\delta(u, c)</tex>. Оказавшись в новом состоянии, отмечаем по сжатым суффиксным ссылкам образцы, которые нам встретились и их позицию (если требуется). Если новое состояние является терминалом, то соответствующие ему образцы тоже отмечаем.<br />
''Примечание.'' Если требуется найти только первое вхождение образца в текст, то существенно ускорить работу алгоритма могут пометки о посещённости узла, т.е. если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.
== Пример реализации ==
Ниже представлена реализация на C++ некоторых функций (используется ленивая рекурсия).<br />
'''Структура вершины:'''
struct Node {
Node* son[26]; // массив сыновей
Node* go[26]; // массив переходов (запоминаем переходы в ленивой рекурсии)
Node* parent; // вершина родитель
Node* suffLink; // суффиксная ссылка (вычисляем в ленивой рекурсии)
Node* up; // сжатая суффиксная ссылка
char charToParent; // символ, ведущий к родителю
bool leaf; // флаг, является ли вершина терминалом
std::vector<int> leafPatternNumber; // номера образцов, за которые отвечает терминал
};
'''Функция, для вычисления суффиксной ссылки:'''
Node* getSuffLink(Node* v) {
if (!v->suffLink) { // если суффиксная ссылка ещё не вычислена
if (v == root || v->parent == root) {
v->suffLink = root;
} else {
v->suffLink = getGo(getSuffLink(v->parent), v->charToParent);
}
}
return v->suffLink;
}
