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