Tries and suffix trees Assume we have one fixed text T of length n and many patterns to look for, each of length m. Searching T for a single pattern with a linear-time matching algorithm costs Θ(n + m). How does building the suffix tree of T once improve on that?

Question

Accepted Answer

Each later pattern can then be matched in Θ(m) time, which does not depend on n.

Answer

It saves space rather than time, because the suffix tree is smaller than T itself.

Answer

Each later pattern can then be matched in Θ(log n) time.

Answer

It does not improve on it: each later search still has to look at the whole of T.

Answer

Each later pattern can then be matched in Θ(1) time, because the tree stores every substring of T explicitly.

Crowdly

Tries and suffix trees Assume we have one fixed text T of length n and many patt...

Want instant access to all verified answers on learning.monash.edu?