Rabin–Karp algorithm
E439883
The Rabin–Karp algorithm is a string-searching technique that uses hashing to efficiently find any one of a set of pattern strings in a text.
Statements (49)
| Predicate | Object |
|---|---|
| instanceOf |
computer science concept
ⓘ
pattern-matching algorithm ⓘ string-search algorithm ⓘ |
| advantage |
efficient for multiple-pattern search
ⓘ
good for plagiarism detection ⓘ good for searching for many patterns simultaneously ⓘ simple to implement ⓘ |
| basedOn | rolling hash ⓘ |
| canBe |
deterministic
ⓘ
randomized ⓘ |
| canFind |
multiple patterns in text
ⓘ
single pattern in text ⓘ |
| category |
randomized algorithms
ⓘ
string algorithms ⓘ |
| comparesWith |
Aho–Corasick algorithm
NERFINISHED
ⓘ
Boyer–Moore algorithm NERFINISHED ⓘ Knuth–Morris–Pratt algorithm NERFINISHED ⓘ |
| designedFor |
pattern matching in text
ⓘ
string searching ⓘ |
| disadvantage |
hash collisions can cause extra comparisons
ⓘ
worst-case time can degrade to O(nm) ⓘ |
| goal |
efficient multi-pattern search
ⓘ
efficient substring search ⓘ |
| hashCollisionProbability | can be made low with large modulus ⓘ |
| hashFunctionType | polynomial rolling hash ⓘ |
| inputParameter |
alphabet size
ⓘ
modulus for hashing ⓘ |
| introducedBy |
Michael O. Rabin
NERFINISHED
ⓘ
Richard M. Karp NERFINISHED ⓘ |
| keyIdea |
compare hash values instead of characters initially
ⓘ
update hash in constant time when sliding window ⓘ use modular arithmetic for hash computation ⓘ |
| operatesOn |
pattern string
ⓘ
text string ⓘ |
| originalPaperTitle | Efficient randomized pattern-matching algorithms ⓘ |
| publicationYear | 1987 ⓘ |
| publishedIn | Communications of the ACM NERFINISHED ⓘ |
| requires | verification of potential matches by direct comparison ⓘ |
| spaceComplexity | O(1) ⓘ |
| timeComplexityAverageCase | O(n + m) ⓘ |
| timeComplexityWorstCase | O(nm) ⓘ |
| typicalUseCase | searching for a pattern in a large text ⓘ |
| usedIn |
information retrieval
ⓘ
intrusion detection systems ⓘ plagiarism detection systems ⓘ search utilities ⓘ text editors ⓘ |
| uses | hashing ⓘ |
| verificationStep | character-by-character comparison on hash match ⓘ |
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.