Introduction
Popular programming languages provide methods or functions which locate a substring in a given string. In C it is the function strstr , the C++ class std::string has the method find , Python's string has methods pos and index , and so on, so forth. All these APIs were designed for one-shot searches. During past decades several algorithms to solve this problem were designed, an excellent page by Christian Charras and Thierry Lecroq lists most of them (if not all). Basically these algorithms could be split into two major categories: (1) based on Deterministic Finite Automaton, like Knuth-Morris-Pratt, Boyer Moore, etc., and (2) based on a simple comparison, like the Karp-Rabin algorithm.
The main problem with these standard algorithms is a silent assumption that comparing a pair of characters, looking up in an extra table and conditions are cheap, while comparing two substrings is expansive.
But current desktop CPUs do not meet this assumption, in particular: