Abstract, ACL2 Seminar talk on "String Searching over Small Alphabets"
We propose a new string searching procedure inspired by the
Boyer-Moore algorithm. The algorithm has larger average shift
amounts than previous variants and guarantees that any character
of the text is read at most once. The performance is especially
favourable when the alphabet size is small. We also discuss
variants of the original idea aimed at practical implementations.
A short introduction to string searching is part of the talk.
See also the UTCS TR-07-62 technical report at: