广义后缀树遍历寻找最长公共子串

Question

我正在处理后缀树。据我所知，我有 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 类似的问题，但该方法似乎非常不同，我不太确定它如何适用于此。

我主要是为了好玩和学习，所以我不一定需要工作代码来替换上面的代码 - 伪代码或任何对我感到困惑的地方的解释也一样。

Answer 1

您对 deepest_shared_edge 的处理是错误的。首先，您在函数开始时所做的分配是内存泄漏，因为您永远不会释放内存。其次，递归调用的结果被忽略，所以它找到的最深边缘都丢失了（虽然你更新了深度，但你没有跟踪最深边缘）。

要解决此问题，您应该将 deepest_shared_edge 作为参考参数传递（就像您对 longest 所做的那样），或者您可以将其初始化为 nullptr，然后检查 return 来自你对 nullptr 的递归调用并适当地更新它。

广义后缀树遍历寻找最长公共子串

Generalised suffix tree traversal to find longest common substring

c++

algorithm

tree

suffix-tree