Efficient Randomized Pattern-Matching Algorithms

By Richard M. Karp, M. Rabin. 1987

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

RUPEE: A fast and accurate purely geometric protein structure search (2018, methodology): “The hash function used is a simplification of the hash function used in the Rabin-Karp algorithm [25].”
Comparison and Evaluation of Clone Detection Tools (2007, unknown): “Ç”
Clone Detection Using Abstract Syntax Suffix Trees (2006, result): “The paper reports the results of several large case studies in which we empirically compare the new technique to other techniques using the Bellon benchmark for clone detectors.”
STAMP: Stanford Transactional Applications for Multi-Processing (2008, methodology): “When matching segments, RabinKarp string matching [23] is used to speed up the comparison.”
The PARSEC benchmark suite: Characterization and architectural implications (2008, methodology): “It uses fast Rabin-Karp fingerprints[24] to detect identity.”
Finding Plagiarisms among a Set of Programs with JPlag (2002, methodology): “|) by applying an idea from the Karp-Rabin pattern matching algorithm [Karp and Rabin, 1987].”
The Algorithm Design Manual (2020, methodology): “The Karp-Rabin algorithm [KR87] uses a hash function to perform string matching in linear expected time.”
The Poly1305-AES Message-Authentication Code (2005, background): “At about the same time, in a slightly different context, Karp and Rabin achieved a key length of 32 bytes for the first message; see [19] and [26].”
Randomized algorithms (1995, unknown): “For example, in pattern-matching applications [Karp and Rabin 1987] it can be shown that two strings are likely to be identical if their fingerprints are identical; 34 • Rajeev Motwani and Prabhakar Raghavan”
Benchmarking modern multiprocessors (2011, background): “It uses rolling fingerprints [45, 77] to segment data based on its contents.”
GapFiller: a de novo assembly approach to fill the gap within paired reads (2012, methodology): “algorithm [21], we can work with numbers modulo q considering equality modulo q only as an indication (necessary condition) that pairs of strings may be the same (i.”
Byte Pair Encoding: a Text Compression Scheme That Accelerates Pattern Matching (1999, methodology): “Karp-Rabin algorithm [23] using the ngerprint function is also applicable to BPE compressed method in a natural way.”
Accurate, scalable in-network identification of p2p traffic using application signatures (2004, background): “Karp-Rabin (KR): This is a probabilistic string matching technique [13] that compares the hash value of the pattern against the hash value of the sub text of a given search text.”
Survey of Research on Software Clones (2006, methodology): “Johnson [30, 31] uses the efficient string matching by Karp and Rabin [32, 33] based on fingerprints.”
A Survey on Software Clone Detection Research (2007, methodology): “Karp-Rabin fingerprinting algorithm [130, 131] is used for calculating the fingerprints of all length n substrings of a text.”