A O(log n) algorithm that looks for a specified element in a sorted (!) array.
It’s an algorithm for searching for a substring within a string. It uses a Bad Match Table to store characters of the pattern we’re searching for (a hashmap). Each character is a key, and the value is the shift from the end of the pattern where the given character can be found. While iterating through source string’s character’s, we’re looking for the last character of the pattern. If we find it, we try to match the rest of the characters. If we find any other character of the pattern, we try to shift the search window to match the postion of the found character with the positon of it in the pattern.
An example of a Bad Match Table for the word “ROOM”:
the “M” character is a bit special - it should be kept outside of the hash map for ease of access since we’re using it all the time in the loop for matching. In the code below I’m just using
pattern[length - 1]to access the last character.
the “R” is on the 3rd index from the right (so, if we find character “R”, we know that we need to shift our search window 3 characters to the right).
the “O” character is there only once. Since keys in a hashmap cannot repeat, we keep only the instance that is positioned the most to the right.
Time Complexity: O(mn) (average - O(n))
The algorithm is efficient, because it skips groups of characters in the input string that have no chance of being a part of the pattern.