Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Rabin–Karp algorithm
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, the Rabin–Karp algorithm or Karp–Rabin algorithm is a <a href="/facts/String-searching_algorithm/RCvwDRle">string-searching algorithm</a> created by <a href="/facts/Richard_M._Karp/XtYCL0nA">Richard M. Karp</a> and <a href="/facts/Michael_O._Rabin/M6NHIb5J">Michael O. Rabin</a> (1987) that uses <a href="/facts/Hash_function/rk6MlCt3">hashing</a> to find an exact match of a pattern string in a text. It uses a <a href="/facts/Rolling_hash/EFQ2cYbP">rolling hash</a> to quickly filter out positions of the text that cannot match the pattern, and then checks for a match at the remaining positions. Generalizations of the same idea can be used to find more than one match of a single pattern, or to find matches for more than one pattern. </p><p>To find a single match of a single pattern, the <a href="/facts/Expected_time/6TqLIMMz">expected time</a> of the algorithm is <a href="/facts/Linear_time/77T62gmf">linear</a> in the combined length of the pattern and text, although its <a href="/facts/Worst-case_complexity/kqzQkwIc">worst-case time complexity</a> is the product of the two lengths. To find multiple matches, the expected time is linear in the input lengths, plus the combined length of all the matches, which could be greater than linear. In contrast, the <a href="/facts/Aho%E2%80%93Corasick_algorithm/huUFNcv8">Aho–Corasick algorithm</a> can find all matches of multiple patterns in worst-case time and space linear in the input length and the number of matches (instead of the total length of the matches). </p><p>A practical application of the algorithm is <a href="/facts/Plagiarism_detection/3lXBIVGK">detecting plagiarism</a>. Given source material, the algorithm can rapidly search through a paper for instances of sentences from the source material, ignoring details such as case and punctuation. Because of the abundance of the sought strings, single-string searching algorithms are impractical. </p>