Я работаю с суффиксными деревьями. Насколько я могу судить, у меня правильно работает алгоритм Укконена для построения обобщенного дерева суффиксов из произвольного числа строк. Сейчас я пытаюсь реализовать метод find_longest_common_substring(), чтобы сделать именно это. Чтобы это сработало, я понимаю, что мне нужно найти самое глубокое общее ребро (с глубиной с точки зрения символов, а не ребер) между всеми строками в дереве, и я несколько дней пытался правильно пройти .
Прямо сейчас у меня есть следующее в С++. Я избавлю вас от всего своего кода, но для контекста я сохраняю ребра каждого узла в unordered_map с именем outgoing_edges, и каждое ребро имеет вектор целых чисел recorded_strings, содержащий целые числа, идентифицирующие добавленные строки. Поле child ребра — это узел, к которому оно направляется, а l и r определяют его крайний левый и правый индексы соответственно. Наконец, current_string_number — это текущее количество строк в дереве.
SuffixTree::Edge * SuffixTree::find_deepest_shared_edge(SuffixTree::Node * start, int current_length, int &longest) {
Edge * deepest_shared_edge = new Edge;
auto it = start->outgoing_edges.begin();
while (it != start->outgoing_edges.end()) {
if (it->second->recorded_strings.size() == current_string_number + 1) {
int edge_length = it->second->r - it->second->l + 1;
int path_length = current_length + edge_length;
find_deepest_shared_edge(it->second->child, path_length, longest);
if (path_length > longest) {
longest = path_length;
deepest_shared_edge = it->second;
}
}
it++;
}
return deepest_shared_edge;
}
При попытке отладки, насколько я могу судить, обход работает в основном нормально, правильно записывает длину пути и самые длинные наборы. Однако по причинам, которые я не совсем понимаю, в самом внутреннем условном выражении deepest_shared_edge иногда кажется, что оно обновляется до ошибочного края. Я подозреваю, что не совсем понимаю, как it->second обновляется на протяжении всей рекурсии. Тем не менее, я не совсем уверен, как это исправить.
