Deterministic Sampling–A New Technique for Fast Pattern Matching

DOI10.1137/0220002MaRDI QIDQ3204065zbMATH OpenOpenAlexFDO

Authors Uzi Vishkin

Publication date 1991

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0220002

zbMATH Keywords

string matchingdeterministic sampling

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Parallel algorithms in computer science (68W10) Theory of data (68P99)

Recommendations

• scientific article; zbMATH DE number 1555939
• Efficient randomized pattern-matching algorithms
• Faster Parallel String Matching via Larger Deterministic Samples
• scientific article; zbMATH DE number 1497852
• Fast pattern-matching on indeterminate strings
• Two-dimensional pattern matching by sampling
• Fast pattern matching method for a bitstream
• A family of fast exact pattern matching algorithms
• Approximating Approximate Pattern Matching

Cited in

(20)

• A string-matching algorithm for the CREW PRAM
• N-cube string matching algorithm with long texts
• Quantum speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching
• Multiple filtration and approximate pattern matching
• Parallel two dimensional witness computation
• Faster broadcasting in unknown radio networks
• Permuted scaled matching
• A note on quantum divide and conquer for minimal string rotation
• Internal pattern matching queries in a text and applications
• Near-optimal quantum algorithms for string problems
• Towards optimal packed string matching
• Designing algorithms by expectations
• New algorithms for the LCA problem and the binary tree reconstruction problem
• Serial and parallel algorithms for order-preserving pattern matching based on the duel-and-sweep paradigm
• On Efficient Gossiping in Radio Networks
• Improved characters distance sampling for online and offline text searching
• Efficient CRCW-PRAM algorithms for universal substring searching
• Quantum pattern matching fast on average
• Efficient string matching on packed texts
• String matching in O( n+ m) quantum time

This page was built for publication: Deterministic Sampling–A New Technique for Fast Pattern Matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3204065)