Geek asks and answers

Finding a substring in a string using the suffix tree ..?

I read that:

The substring search, pat [1..m], in txt [1..n], can be resolved in O (m) time (after the suffix tree for txt was built in O (n) time.

but at each point we will need to choose which branch to take, since in the n-ary tree, in each node, we will have to compare with all the max-n pointers in this node to decide whether to take the branch. Will this not bring the n factor of complexity of this algorithm, somehow in the picture

Then, as stated above, what substring can be found in O (m)?

What am I missing here?

+3
source share
2 answers

Then, as stated above, what substring can be found in O (m)?

Inaction. You are right that the search execution time in the suffix trees is more complicated than just O (m).

, O (m), : node O (1), , (, ), .

, , ++ , (char) 256 . node :

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

current_character , node, children - . , node u, c. node :

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

, (, ). , O (m).

+5

, ,

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

O (m).

0

More articles:


All Articles