Menu
Wondering, if I want to replace strstr with a better string matching algorithm, like KMP or Boyer Moore, is there one in C++ or do we have to write on our own?
Wondering, what is the practical string matching function that everyone uses other than strstr?
This is with respect to C++/STL under Unix/Linux platform.
855
KMP Algorithm has a guaranteed worst-case linear-time performance, i.e. both time and space complexity: O(m + n) in worst case. But, Boyer Moore can be much faster than KMP, but only on certain inputs that allow many characters to be skipped (similar to the example in the 2nd point).
Unlike the previous pattern searching algorithms, the Boyer Moore algorithm starts matching from the last character of the pattern. In this post, we will discuss the bad character heuristic and the Good Suffix heuristic in the next post. Pattern P moves past the mismatched character.
Knuth Morris Pratt (KMP) is an algorithm, which checks the characters from left to right. When a pattern has a sub-pattern appears more than one in the sub-pattern, it uses that property to improve the time complexity, also for in the worst case. The time complexity of KMP is O(n).
I haven't seen many that use features specific to C++, but there are quite a few implementations of KMP and (especially) variants of Boyer-Moore (e.g., Boyer-Moore-Horspool) around that are easily usable from C++.
50
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
