Rabin–Karp algorithm
In computer science, the Rabin–Karp algorithm or Karp–Rabin algorithm is a string-searching algorithm created by Richard M. Karp and Michael O. Rabin that uses hashing to find an exact match of a pattern string in a text. It uses a rolling hash 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.
- Author1Link
- enRichard M. Karp
- Author2Link
- enMichael O. Rabin
- Class
- String-searching algorithm
- Comment
- enIn computer science, the Rabin–Karp algorithm or Karp–Rabin algorithm is a string-searching algorithm created by Richard M. Karp and Michael O. Rabin that uses hashing to find an exact match of a pattern string in a text. It uses a rolling hash 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.
- First
- enMichael O.
- enRichard M.
- Has abstract
- enIn computer science, the Rabin–Karp algorithm or Karp–Rabin algorithm is a string-searching algorithm created by Richard M. Karp and Michael O. Rabin that uses hashing to find an exact match of a pattern string in a text. It uses a rolling hash 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. To find a single match of a single pattern, the expected time of the algorithm is linear in the combined length of the pattern and text,although its worst-case time complexity 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 Aho–Corasick algorithm 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). A practical application of the algorithm is detecting plagiarism. 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.
- Hypernym
- String
- Is primary topic of
- Rabin–Karp algorithm
- Label
- enRabin–Karp algorithm
- Last
- enKarp
- enRabin
- Link from a Wikipage to an external page
- books.google.com/books%3Fid=Uk9tyXgQME8C&pg=PA205%7C
- yurichev.com/news/20210205_rolling_hash/
- courses.csail.mit.edu/6.006/spring11/rec/rec06.pdf
- Link from a Wikipage to another Wikipage
- Aho–Corasick algorithm
- ASCII
- Big-O notation
- Bloom filter
- Boyer–Moore string search algorithm
- Boyer–Moore string-search algorithm
- Cambridge, Massachusetts
- Category:Hashing
- Category:String matching algorithms
- Computer science
- Data type
- Expected time
- False positive
- Hash collision
- Hash function
- Hash value
- Introduction to Algorithms
- Knuth–Morris–Pratt algorithm
- Linear time
- Modular arithmetic
- Plagiarism detection
- Rabin fingerprint
- Rolling hash
- Set data structure
- String searching algorithm
- String-searching algorithm
- Worst-case complexity
- Name
- enRabin-Karp algorithm
- SameAs
- Algorithme de Rabin-Karp
- Algoritmo di Rabin-Karp
- Algoritmo Karp-Rabin
- Algoritmul Rabin-Karp
- Algorytm Karpa-Rabina
- m.032sbg
- PudA
- Q1384131
- Rabin-Karp-Algorithmus
- Rabin-Karps algoritm
- Rabinův–Karpův algoritmus
- Алгоритм Рабина — Карпа
- Алгоритм Рабіна — Карпа
- Рабин-Карп алгоритам
- الگوریتم جستجوی رشته رابین-کارپ
- خوازمية رابين وكارب
- ขั้นตอนวิธีราบิน–คาร์ป
- ラビン-カープ文字列検索アルゴリズム
- 拉宾-卡普算法
- Subject
- Category:Hashing
- Category:String matching algorithms
- Time
- enplus preprocessing time
- WasDerivedFrom
- Rabin–Karp algorithm?oldid=1111221583&ns=0
- WikiPageLength
- 14053
- Wikipage page ID
- 684698
- Wikipage revision ID
- 1111221583
- WikiPageUsesTemplate
- Template:Cite book
- Template:Cite journal
- Template:Cite web
- Template:Harvs
- Template:Infobox algorithm
- Template:Main
- Template:No footnotes
- Template:Reflist
- Template:Short description
- Template:Strings
- Year
- 1987