Efficient randomized pattern-matching algorithms
From MaRDI portal
Publication:3799643
DOI10.1147/rd.312.0249zbMath0653.68054OpenAlexW1972418517WikidataQ55881427 ScholiaQ55881427MaRDI QIDQ3799643
Michael O. Rabin, Richard M. Karp
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
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Formal languages and automata (68Q45)
Related Items
Compressed string dictionary search with edit distance one, Efficient string matching with k mismatches, Sensitivity analysis and efficient method for identifying optimal spaced seeds, Sublinear approximate string matching and biological applications, When can you fold a map?, Distributed algorithms in synchronous broadcasting networks, Scaled and permuted string matching, Permuted scaled matching, Efficient computation of sequence mappability, Indexing and querying color sets of images, Access, Rank, and Select in Grammar-compressed Strings, Dictionary Matching in a Stream, Approximating LZ77 via Small-Space Multiple-Pattern Matching, Document listing on repetitive collections with guaranteed performance, Time-Space Trade-Offs for Longest Common Extensions, Fast exact string matching algorithms, Efficient multiway radix search trees, Multiple filtration and approximate pattern matching, Fast algorithms for abelian periods in words and greatest common divisor queries, Fast string matching with k differences, Fingerprints in compressed strings, Matching patterns in strings subject to multi-linear transformations, Can Burrows-Wheeler transform be replaced in chain code compression?, Weighted approximate parameterized string matching, Space-time trade-offs for finding shortest unique substrings and maximal unique matches, Kings, Name Days, Lazy Servants and Magic, Longest Common Extensions in Sublinear Space, Succinct Non-overlapping Indexing, Dictionary Matching with Uneven Gaps, Simple real-time constant-space string matching, More Than 1700 Years of Word Equations, Longest common substring with approximately \(k\) mismatches, Various improvements to text fingerprinting, \(p\)-suffix sorting as arithmetic coding, Efficient index for retrieving top-\(k\) most frequent documents, Compact q-gram profiling of compressed strings, Layouts for improved hierarchical parallel computations, Simple, compact and robust approximate string dictionary, Fast and flexible packed string matching, Time-space trade-offs for Lempel-Ziv compressed indexing, Efficient computation of shortest absent words in complete genomes, A compact representation of nondeterministic (suffix) automata for the bit-parallel approach, An analysis of the Karp-Rabin string matching algorithm, Dictionary matching with a bounded gap in pattern or in text, Dynamic and internal longest common substring, Time-space trade-offs for longest common extensions, Fast algorithms for single and multiple pattern Cartesian tree matching, Block trees, Hardness of optimal spaced seed design, Universal compressed text indexing, Solutions to twisted word equations and equations in virtually free groups, An introduction to randomized algorithms, A faster quick search algorithm, Improved space-time tradeoffs for approximate full-text indexing with one edit error, Improving deduplication techniques by accelerating remainder calculations, String-Matching and Alignment Algorithms for Finding Motifs in NGS Data, A fast algorithm for string matching with mismatches, Streaming pattern matching with \(d\) wildcards, On the string matching with \(k\) mismatches, Approximate string-matching with \(q\)-grams and maximal matches, Real-Time Streaming String-Matching, Simple Real-Time Constant-Space String Matching, Designing optimal- and fast-on-average pattern matching algorithms, An artificial neural network based approach for online string matching/filtering of large databases, Resilient dynamic programming, Execution of logic programs by iterative-deepening A\(^*\) SLD-tree search, A randomized numerical aligner (rNA), Fast searching in packed strings, Permuted pattern matching algorithms on multi-track strings, Identifying periodic occurrences of a template with applications to protein structure, Fast two-dimensional pattern matching, Content-dependent chunking for differential compression, the local maximum approach, Bounded similarity querying for time-series data, Missing pattern discovery, LCS approximation via embedding into locally non-repetitive strings, Improving on-line construction of two-dimensional suffix trees for square matrices, Fast parallel and serial multidimensional approximate array matching, Two-dimensional pattern matching against local and regular-like picture languages, The circulant hash revisited, Succinct non-overlapping indexing, Index structures for fast similarity search for symbol strings, Efficient and secure outsourced approximate pattern matching protocol, Dynamic determination of variable sizes of chunks in a deduplication system, Streaming \(k\)-mismatch with error correcting and applications, LCS Approximation via Embedding into Local Non-repetitive Strings, Fast Searching in Packed Strings, Alphabet-independent optimal parallel search for three-dimensional patterns, A Very Fast String Matching Algorithm Based on Condensed Alphabets, Top tree compression of tries, Tight tradeoffs for real-time approximation of longest palindromes in streams, Finger search in grammar-compressed strings, Average-optimal string matching, Time-space-optimal string matching, Sliding suffix tree, Constrained tree inclusion, Quantum algorithms for string processing, Sending compressed messages to a learned receiver on a bidirectional line., Approximate hashing for bioinformatics, Computing the maximum exponent in a stream, Streaming dictionary matching with mismatches, Fast algorithms for two dimensional and multiple pattern matching, Dynamic algorithms for the Dyck languages, A Bit-Parallel Exact String Matching Algorithm for Small Alphabet, Engineering Practical Lempel-Ziv Tries, String Indexing with Compressed Patterns, Efficient construction of the BWT for repetitive text using string compression, Classical and quantum algorithms for constructing text from dictionary problem, On using q-gram locations in approximate string matching, Balancing run-length straight-line programs, Near-optimal search time in \(\delta \)-optimal space, and vice versa, Classical and Quantum Algorithms for Assembling a Text from a Dictionary, Unnamed Item, Near-optimal quantum algorithms for string problems, Unnamed Item, Complexity of Matching Sets of Two-Dimensional Patterns by Two-Dimensional On-Line Tessellation Automaton, Unnamed Item, Unnamed Item, Unnamed Item, Filtering Multi-set Tree: Data Structure for Flexible Matching Using Multi-track Data, Practical Performance of Space Efficient Data Structures for Longest Common Extensions., Towards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams, On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation, Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries, Data compression with long repeated strings, Compression in the presence of shared data, Periodicity in data streams with wildcards, Bouma2 – A High-Performance Input-Aware Multiple String-Match Algorithm, Repetition Detection in a Dynamic String, A New String Matching Algorithm, Streaming Dictionary Matching with Mismatches, Searching Long Repeats in Streams, Quasi-Periodicity in Streams, Unnamed Item, Parallel String Matching
