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

Question

我读过:

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

但是在每个点上,我们必须选择要采用的分支,因此在n-ary树中,在每个节点处,我们必须与该节点中的所有最大n个指针进行比较,以决定采用哪个分支.这不会给这个算法的复杂性带来因素,不知何故在图片中

那么如何在O(m)中找到子串呢？

我在这里错过了什么？

Answer 1

那么如何在O(m)中找到子串呢？

遗漏.你是正确的,在后缀树中搜索的运行时间比仅仅O(m)更复杂.

但是,如果我们权衡空间需求,它确实可以加速到O(m):我们需要将每个节点的搜索下调到O(1),我们可以通过使用适当的数据结构(例如数组)来实现)它为我们提供了恒定时间内每个字母的适当子树.

例如,假设您使用C++进行实现,而您的character(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).