Efficient randomized pattern-matching algorithms
From MaRDI portal
Publication:3799643
DOI10.1147/RD.312.0249zbMATH Open0653.68054OpenAlexW1972418517WikidataQ55881427 ScholiaQ55881427MaRDI QIDQ3799643FDOQ3799643
Richard Karp, Michael O. Rabin
Publication date: 1987
Published in: IBM Journal of Research and Development (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/c47d151f09c567013761632c89e237431c6291a2
Recommendations
Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)
Cited In (only showing first 100 items - show all)
- Sensitivity analysis and efficient method for identifying optimal spaced seeds
- Fast two-dimensional pattern matching
- Compact q-gram profiling of compressed strings
- Title not available (Why is that?)
- A randomized algorithm for approximate string matching
- Execution of logic programs by iterative-deepening A\(^*\) SLD-tree search
- Improving on-line construction of two-dimensional suffix trees for square matrices
- Efficient index for retrieving top-\(k\) most frequent documents
- Fast and flexible packed string matching
- Layouts for improved hierarchical parallel computations
- Simple, compact and robust approximate string dictionary
- A compact representation of nondeterministic (suffix) automata for the bit-parallel approach
- Content-dependent chunking for differential compression, the local maximum approach
- When can you fold a map?
- Hardness of optimal spaced seed design
- Improving deduplication techniques by accelerating remainder calculations
- Compressed string dictionary search with edit distance one
- Approximate string-matching with \(q\)-grams and maximal matches
- Fast searching in packed strings
- LCS Approximation via Embedding into Local Non-repetitive Strings
- Efficient string matching with k mismatches
- Sublinear approximate string matching and biological applications
- On using q-gram locations in approximate string matching
- Fast string matching with k differences
- Bounded similarity querying for time-series data
- Improved space-time tradeoffs for approximate full-text indexing with one edit error
- Missing pattern discovery
- Fast exact string matching algorithms
- Multiple filtration and approximate pattern matching
- Time-Space Trade-Offs for Longest Common Extensions
- Permuted scaled matching
- Simple real-time constant-space string matching
- Streaming pattern matching with \(d\) wildcards
- \(p\)-suffix sorting as arithmetic coding
- Indexing and querying color sets of images
- Dictionary Matching with Uneven Gaps
- Fast algorithms for single and multiple pattern Cartesian tree matching
- Various improvements to text fingerprinting
- Title not available (Why is that?)
- LCS approximation via embedding into locally non-repetitive strings
- A faster quick search algorithm
- Average-optimal string matching
- Scaled and permuted string matching
- Fast algorithms for abelian periods in words and greatest common divisor queries
- Fast parallel and serial multidimensional approximate array matching
- Succinct non-overlapping indexing
- Data compression with long repeated strings
- Real-Time Streaming String-Matching
- Time-space-optimal string matching
- Title not available (Why is that?)
- Succinct Non-overlapping Indexing
- Space-time trade-offs for finding shortest unique substrings and maximal unique matches
- An analysis of the Karp-Rabin string matching algorithm
- Title not available (Why is that?)
- Fast Searching in Packed Strings
- Repetition Detection in a Dynamic String
- Time-space trade-offs for longest common extensions
- An introduction to randomized algorithms
- Designing optimal- and fast-on-average pattern matching algorithms
- Resilient dynamic programming
- Universal compressed text indexing
- Approximating LZ77 via Small-Space Multiple-Pattern Matching
- Constrained tree inclusion
- Simple Real-Time Constant-Space String Matching
- Fast algorithms for two dimensional and multiple pattern matching
- Longest Common Extensions in Sublinear Space
- Efficient computation of shortest absent words in complete genomes
- On the string matching with \(k\) mismatches
- Deterministic Sampling–A New Technique for Fast Pattern Matching
- A fast algorithm for string matching with mismatches
- Efficient indexes for jumbled pattern matching with constant-sized alphabet
- Matching patterns in strings subject to multi-linear transformations
- Finger search in grammar-compressed strings
- Sending compressed messages to a learned receiver on a bidirectional line.
- The circulant hash revisited
- Efficient computation of sequence mappability
- Suffix arrays for multiple strings: a method for on-line multiple string searches
- Block trees
- Engineering Practical Lempel-Ziv Tries
- Sliding suffix tree
- Fingerprints in compressed strings
- A New String Matching Algorithm
- Permuted pattern matching algorithms on multi-track strings
- Approximate hashing for bioinformatics
- Computing the maximum exponent in a stream
- Streaming dictionary matching with mismatches
- Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries
- Complexity of Matching Sets of Two-Dimensional Patterns by Two-Dimensional On-Line Tessellation Automaton
- Parallel String Matching
- A Bit-Parallel Exact String Matching Algorithm for Small Alphabet
- Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
- Periodicity in data streams with wildcards
- Streaming \(k\)-mismatch with error correcting and applications
- Alphabet-independent optimal parallel search for three-dimensional patterns
- Classical and quantum algorithms for constructing text from dictionary problem
- Classical and Quantum Algorithms for Assembling a Text from a Dictionary
- Kings, Name Days, Lazy Servants and Magic
- String-Matching and Alignment Algorithms for Finding Motifs in NGS Data
- Weighted approximate parameterized string matching
- Compression in the presence of shared data
This page was built for publication: Efficient randomized pattern-matching algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3799643)
