Rabin–Karp algorithm: Difference between revisions

Revision as of 07:10, 14 November 2004

Revision as of 07:11, 14 November 2004

Line 5:

== Shifting substrings search and competing algorithms ==

The basic problem the algorithm addresses is finding a fixed substring of length ''m'' within a text of length ''n''; for example, finding the string "sun" in the sentence "Hello sunshine in this vale of tears." The simplest conceivable algorithm for this task just looks for the substring at all possible positions:

{{wikicode}}

'''1''' '''function''' NaiveSearch(''string'' s[1..n], ''string'' sub[1..m])

'''2''' '''for''' i '''from''' 1 '''to''' n

Line 14 ⟶ 15:

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 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.

== Use of hashing for shifting substring search ==

Line 23 ⟶ 24:

The algorithm is as shown:

{{wikicode}}

'''1''' '''function''' RabinKarp(''string'' s[1..n], ''string'' sub[1..m])

'''2''' hsub := hash(sub[1..m])