online advertising

Friday, June 26, 2015

Road to suffix tree (11)

Okay, for real, two more tricks, done.

This rule is a real time saver. I call it, once no-op, always no-op within the same phase.

Consider the no-op rule is applied for the string aX. What does that imply?

It means the string aX is already in the tree, inserted in a previous phase.

But if aX is inserted in a previous phase, then so is all the suffixes of aX. So we can simply ignore all the insertion after we see the first no-op because the rest will be no-op as well.

In the book, this trick is called "Rule 3 is a show stopper".

A very simple solution based on returning a flag is used to indicate whether the subsequent insertion can be skipped!

This result in SuffixTree7!

No comments :

Post a Comment