Shift-Or String Matching With Super-Alphabets

Given a text T [1 : : : n] and a pattern P [1 : : : m] over some alphabet of size , we want to nd all the (exact) occurrences of P in T . The well-known shift-or algorithm solves this problem in time O(ndm=we), where w is the number of bits in machine word, using bit-parallelism. We show how to extend the bit-parallelism in another direction, using super-alphabets. This gives a speed-up by a factor s, where s is the number of characters processed simultaneously. The algorithm is implemented, and we show that it works well in practice too. The result is the fastest known algorithm for exact string matching for short patterns and small alphabets