This algorithm works well in many practical cases, but fails spectacularly on certain examples, such as searching for a string of 10,000 "a"s followed by a "b" in a string of 10 million "a"s, in which case it exhibits its worst-case [[Big-O notation|Ω]](''mn'') time.
The [[Knuth-Morris-Pratt algorithm]] isreduces anthis elegantto elaborationΩ(''n'') ontime thisusing naiveprecomputation algorithmto thatexamine useseach precomputedtext datacharacter toonly once; the [[Boyer-Moore string search algorithm|Boyer-Moore algorithm]] skipskips forward not by 1 character, but by as many as possible for the search to succeed, effectively decreasing the number of times we iterate through the outer loop, so that the number of characters examined can be as small as ''n/m'' in the best case. However, The Rabin-Karp algorithm focuses instead on speeding up lines 3-6, as we'll discuss in the next section.
== Use of hashing for shifting substring search ==
