Science Fair Project Encyclopedia
Horspool's algorithm for string matching
Horspool's algorithm is an algorithm for finding substrings in strings.
It is a simplification of the Boyer-Moore algorithm which is related to the Knuth-Morris-Pratt algorithm. The algorithm trades space for time in order to obtain an average case complexity of
- O(N)
on random text, although it has
- O(MN)
in the worst case.
Last updated: 06-23-2005 02:35:01
10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details