algorithm - 使用后缀树在字符串中搜索子字符串..？

Question

我读过:

在 txt[1..n] 中搜索一个子字符串 pat[1..m]，可以在 O(m) 时间内解决(在 txt 的后缀树已经在 O( n) 次).

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

那上面怎么说可以在O(m)中找到子串呢？

我在这里错过了什么？

Answer 1

Then how above it says that substring can be found in O(m)?

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

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

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

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

现在，current_character 指的是通向当前节点的分支的字符，而children 是一个子节点数组。在搜索过程中，假设您当前位于节点 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)。