Overview of String Matching Algorithms
Explore different string matching algorithms including naive and Boyer-Moore methods, and understand how C++17 improves pattern searching with new std::search options to boost efficiency.
We'll cover the following...
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) |