As the paper itself says, this is still N^2 log N worst case :) Note that these are all variants of general algorithm I posted, and more generally, variants of

As the paper itself says, this is still N^2 log N worst case :) Note that these are all variants of general algorithm I posted, and more generally, variants of tricks used in boyer-moore (though hunt's work predates boyer-moore, that's the easiest way to describe it), which means they try to skip parts of the text they can prove can't match. Because they can't always do so, they don't change the worst case time bound, only various other time bounds.