online advertising

Friday, June 26, 2015

Road to suffix tree (09)

In the last post we left a question open. What so interesting about the suffix links?

Imagine you are doing an extension to insert aXY, in the next iteration so will be inserting XY, if you knew the suffix link of the node represented by aX, what would you do?

Follow the suffix link and start the search there, right?

But wait, suppose we followed the suffix link, how much of the string to insert can I skip? With the current structure, there is no way to tell by just following the suffix link, so we need the depth information to pass as well when we follow a suffix link.

Luckily, by the time we found a suffix link, we are searching in the tree, so we actually know what is the current number of character that we can skip!

This result in SuffixTree5.

No comments :

Post a Comment