Shift-or string matching with super-alphabets
Given a text T [1... n] and a pattern P[1... m] over some alphabet Sigma of size sigma, we want to find all the (exact) occurrences of P in T. The well-known shift-or algorithm solves this problem in time O(n[m/omega]), where omega 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. (C) 2003 Elsevier B.V. All rights reserved.
string matching algorithms bit-parallelism