pattern: EXAMPLE text: HERE IS A SIMPLE EXAMPLEWe can show you the Knuth-Pratt-Morris algorithm and we can show you the Boyer-Moore algorithm.

Our algorithm has the peculiar property that, roughly speaking, the longer the pattern is, the faster the algorithm goes. Furthermore, the algorithm is ``sublinear'' in the sense that it generally looks at fewer characters than it passes. The algorithm is described in

- A Fast String Searching
Algorithm, with R.S. Boyer.
*Communications of the Association for Computing Machinery*,**20**(10), 1977, pp. 762-772.

However, in 2007, Matyas Sustik and I thought of an apparently new variation that gives very good performance on small alphabets and has a small table. The algorithm is described in UTCS Tech Report TR-07-62, ``String Searching over Small Alphabets.''

[Best Ideas]
[Publications]
[Research]
[Home]