Overview of String Matching Algorithms
This lesson will provide an overview of matching algorithms.
We'll cover the following...
String Matching
String-matching consists of finding one or all of the occurrences of a string (“pattern”) in a text. The strings are built over a finite set of characters, called “alphabet”.
There are lots of algorithms that solve this problem; here’s a short list from Wikipedia:
| Algorithm | Preprocessing | Matching | Space |
|---|---|---|---|
| Naive string-search | none | O(nm) |
none |
| Rabin–Karp | O(m) |
average O(n + m), worst O((n−m)m) |
O(1) |
| Knuth–Morris–Pratt | O(m) |