0
我正在处理后缀树。据我所知，我已经正确运行了Ukkonen的算法，可以从任意数量的字符串中构建通用后缀树。我现在试图实现一个find_longest_common_substring()方法来做到这一点。为了这个工作，我知道我需要在树中的所有字符串之间找到最深的共享边（字符深度而不是边），并且我一直在挣扎几天来获得遍历权。通用后缀树遍历查找最长公共子串
现在我在C++中有以下内容。我会尽量提供所有代码，但对于上下文，我将每个节点的边缘保留在一个名为outgoing_edges的unordered_map中，并且每个边都有一个包含识别添加的字符串的整数的整数的向量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在整个递归中如何更新。但我不太清楚如何去解决这个问题。
我知道this类似的问题，但方法似乎有足够的差异，我不太确定它是如何适用于此。
我主要是为了好玩和学习，所以我不一定需要工作代码来替换上面的伪代码，或者只是对我困惑的地方的任何解释都一样。