Реализации алгоритмов/Поиск в суффиксном дереве

C++

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;
}

См. также

• Алгоритм Укконена.