Deterministic Sampling–A New Technique for Fast Pattern Matching

DOI10.1137/0220002zbMath0716.68074OpenAlexW1991454799MaRDI QIDQ3204065

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

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

Related Items (15)

New algorithms for the LCA problem and the binary tree reconstruction problem ⋮ Designing algorithms by expectations ⋮ Permuted scaled matching ⋮ Parallel two dimensional witness computation ⋮ Multiple filtration and approximate pattern matching ⋮ String matching in \(\tilde O(\sqrt n+\sqrt m)\) quantum time ⋮ Improved characters distance sampling for online and offline text searching ⋮ Near-optimal quantum algorithms for string problems ⋮ Towards optimal packed string matching ⋮ Efficient string matching on packed texts ⋮ Quantum pattern matching fast on average ⋮ A string-matching algorithm for the CREW PRAM ⋮ Efficient CRCW-PRAM algorithms for universal substring searching ⋮ On Efficient Gossiping in Radio Networks ⋮ Faster broadcasting in unknown radio networks

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