Content deleted Content added
m The |
→Shifting substrings search and competing algorithms: Fix example |
||
Line 15:
'''7''' '''return''' not found
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.
[[Knuth-Morris-Pratt algorithm]] is an elegant elaboration on this naive algorithm that uses precomputed data to skip 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. However, Rabin-Karp focuses instead on speeding up lines 3-6, as we'll discuss in the next section.
| |||