We have a string of length \(N\), and wish to find an \(M\) character string in it.
Brute Force
Keep moving through the string till the first letter in the pattern is matched. Then keep checking the subsequent characters.
Problem: If your pattern is, say, 20 characters, and the first 19 match, then you have to backtrack 19 characters and start all over. This leads to a worst case complexity of \(MN\).
And backtracking is not always feasible (e.g. a live stream over the Internet). You’d have to keep a buffer of the last \(M\) characters.
Knuth-Morris-Pratt Algorithm
The cost of a backup could be diminished if we had a means to know how far back to go. If your pattern is \(M\) characters, you may get away by going back only a few characters. A concrete example: Say you want to find the string AAAABB. Let’s say the text has AAAAAABB. At the 5th character, we have a mismatch, but we need not go back and start from the 2nd A. We can just note that we still have 4 contiguous A‘s and continue.
The general way to handle this is to have a finite state machine, where decisions are made based on what the next character is. This way, we never backtrack on the main string!
The complexity is \(O(M+N)\) (\(M\) is needed to initially construct a desired finite state machine). We need extra space of \(RM\).
Boyer-Moore Algorithm
The basic gist is that if you don’t get a match after, say, 5 characters, you may be able to continue your search from character 6 (under ideal conditions). Even if you backtrack, you may not need to backtrack as much. There’s a scheme to calculate how much to jump.
On average, this takes \(O(N/M)\) time (which is amazing). But the worst case is still as bad as the brute force. If we make a hybrid of this with the KMP algorithm, we could get it down to about \(3N\).
Rabin-Karp Algorithm
The Rabin-Karp algorithm utilizes hashing.
Say your pattern is 26535. Pick a high prime (e.g. 997). Take the mod of it to get 613.
Now as you iterate through your text, after you encounter 5 digits, calculate the modulus. If it doesn’t match, update with the next entry (easy to do - you don’t need to go through all 5 characters again).
If you get the same value, you may have a match. You could explicitly look at the characters, or you could probabilistically declare a match. The error likelihood will be roughly \(1/Q\) where \(Q\) is your large prime.
For general text, you calculate the hash using \(a_{n}R^{n}+a_{n-1}R^{n-1}+\cdots+a_{1}R+a_{0} % Q\) where \(R\) is the size of your alphabet. You can calculate the polynomial in linear time using Horner’s Rule. Updating when you get the next character is also incrementally linear.
Pick a large \(Q\), but not so large that you risk overflow.
The algorithm is linear, but perhaps not as fast as some other methods.