void SuffixTree::CountIndex(Node *node, vector<int> &vec)
{
if (!node) // конец рекурсии: пустое поддерево
return;
for (auto it : node->children) // рекурсивный вызов для всех поддеревьев
CountIndex(it.second, vec);
if (node->suffix_index != -1) // как дошли до листа, добавляем в вектор его индекс
vec.push_back(node->suffix_index);
}
void SuffixTree::Search(string &pat, int patNum)
{
Node *current = root; // начинаем поиск из корня
for (auto it = pat.begin(); it != pat.end();) // итерируемся по паттерну, пока можем
{
auto find = current->children.find(*it);
// исходит ли из текущей ноды дуга, начинающаяся символом *it?
if (find != current->children.end())
{
// если да, то перескочим на эту дугу
current = find->second;
// и пробежим все ее символы
for (int j = current->start; j <= *current->end && it != pat.end(); j++, ++it)
{
// мисмач - выходим из функции, паттерна в тексте нет
if (text[j] != *it)
return;
}
}
else
// мисмач - выходим из функции, паттерна в тексте нет
return;
}
vector<int> ind; // массив индексов листьев
CountIndex(current, ind); // которые содержатся в поддереве с вершиной-корнем current,
// в конце которой паттерн полностью поматчился с путевой меткой этой вершины
sort(ind.begin(), ind.end());
cout << patNum << ": " << ind[0] + 1;
for (auto &pos : ind) {
if (pos == ind[0]) continue;
cout << ", " << pos + 1;
} cout << endl;
}
