online advertising

Friday, June 26, 2015

Road to suffix tree (10)

Part 10, really? Fortunately, we are going to finish the series soon. A few more tricks, and we are done.

In this post we will speed up the search even more. Notice that we are searching in the link character by character, and we require all characters in a link to match the key because we knew the search string is already in the tree. What if we just skip through it.

Concretely, when we reach a node, determine the longest length we can move by min(remainingSearchKeyLength, edgeLength), and we can just increase the cursor to reach there right away!

Also, we can save just the substring indexes in the edge, there is no point constructing a storing the whole substring!

This results in SuffixTree6.

In the book - this trick is called the skip count trick. A neat trick indeed.

No comments :

Post a Comment