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: http://www.cs.utexas.edu/research/publications/.