c++ - 如何使用后缀树查找所有匹配子串的索引？

Question

我从这个惊人的 answer 创建了一个后缀树.它就像一个魅力!

现在，如果我在“This cat is a pretty cat”中查找“cat”，它将返回 5 作为“cat”的首次出现，起始索引为 5。

但我找不到一种方法来跟踪要创建的算法中的所有后缀。所以基本上，我可以找到第一个匹配项的索引，但不能找到所有不同的匹配项。

目前，我有:

class Edge
{
    int textIndexFrom;
    Node* nodefrom;
    Node* nodeTo;
    int textIndexTo;
}

class Node
{
    std::map<char,Edge*> m_childEdges;
    Edge* m_pParentEdge;
    Node* m_pLinkedNode;
}

我只是把相关的变量放在上面的代码中。为了存储不同的起始位置，我想在 Edge 中需要一个 std::vector，但我不知道何时添加新索引。我们可能会使用事件点，但使用后缀链接，它就变得棘手了。

谁能解释一下？

Answer 1

我假设您为字符串 S$ 构建了一个后缀树，其中 $ 是 S 中不存在的一些特殊字符。 $ 字符确保每个后缀在树中都有自己的叶子。单词w在S中出现的次数就是w子树中的叶子数。

我认为存储每个边缘/节点中的所有起始位置需要二次内存。例如，如果 T 恰好是完全平衡的二叉树，那么在第 0 级(根)上你有 n 个条目，在第 1 级上你有 2 * n/2 条目等。求和后得到 n^2。这需要证明，所以如果我错了请纠正我。

相反，我认为最好将所有叶子保存在一个列表中，以便它们出现在树的 dfs 遍历中(如果您绘制树的图片，则从左到右)。并且在每个节点 v 中保留 2 个指向该列表元素的指针。 First 应该指向 v's 子树的第一个叶子，second 应该指向 v's 子树的最后一个叶子。所有这些都可以通过简单的 dfs 程序计算出来。现在，如果例如“cat”恰好位于某个边缘的中间，则通过该边缘到达某个节点 v 并从该节点获取叶子。此外，在每片叶子中，您应该存储从根到那片叶子的路径长度。它将帮助您找到特定“猫”出现的位置。