3

我读过：

在 txt[1..n] 中搜索子字符串 pat[1..m] 可以在 O(m) 时间内解决（在 O(n) 时间内构建 txt 的后缀树之后）。

但是在每一点，我们都必须选择要采用哪个分支，所以就像在 n 叉树中一样，在每个节点上，我们必须与该节点中的所有最大 n 个指针进行比较，以决定采用哪个分支。这会不会在这个算法的复杂性中带来 n 个因素，不知何故在图片中

那么上面如何说可以在 O(m) 中找到子字符串？

我在这里想念什么？

4

2 回答 2

5

那么上面如何说可以在 O(m) 中找到子字符串？

由于遗漏。你是正确的，在后缀树中搜索的运行时间比 O(m) 更复杂。

但是，如果我们权衡空间要求，它确实可以加速到 O(m)：我们需要将每个节点的搜索降低到 O(1)，我们可以通过使用适当的数据结构（例如数组）来做到这一点) 这为我们在恒定时间内为每个字母提供了适当的子树。

例如，假设您使用 C++ 进行实现，并且您的字符 ( char) 可以包含 256 个不同的值。那么一个节点的实现可能如下所示：

struct node {
    char current_character;
    node* children[256];
};

现在，current_character指的是指向当前节点的分支的字符，并且children是一个子节点数组。在搜索过程中，假设您当前在 node u，输入文本中的下一个字符是c。然后您将选择下一个节点，如下所示：

node* next = u->children[c];
if (next == 0) {
    // Child node does not exist => nothing found.
}
else {
    u = next;
    // Continue search with next …
}

当然，这仅适用于非常小的字母表（例如基因组序列的 DNA）。在最常见的情况下，后缀树的最坏情况运行时间确实高于 O(m)。

于 2011-06-08T09:14:38.530 回答
0

如果指向子元素的指针在由字母索引的数组中，则每个模式字母只需要恒定时间

node = tree root
FOR i in 1..m
   node = child[pat[i]]

所以复杂度是O(m)。

于 2011-06-08T09:12:57.130 回答