On 05/24/2016 08:38 AM, Andrei Alexandrescu wrote:
One somewhat unrelated thing that can be done with Boyer-Moore: use a constant-length skip array instead of dynamic allocation. Upon saturation, continue with brute force. -- Andrei
Another idea: in every searched string there is one specific index that offers the most information to a failed search, allowing for a large skip. Roughly speaking it's the largest index around which there are many characters not seen elsewhere in the searched string. (In a string with all distinct characters, that would be the last character.) If that offset is cheap to compute and offers a good skip, a search starting from that index would be very fast. -- Andrei
