The Complexity of Pattern Matching for a Random String

DOI10.1137/0208029MaRDI QIDQ3854624zbMATH OpenOpenAlexFDO

Authors Andrew Chi-Chih Yao

Publication date 1979

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

Full work available at URL https://semanticscholar.org/paper/9cefac9f2bcc75cd36702fe01476d469a51f9a66

zbMATH Keywords

average case complexitystring matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited in

(38)

• Average-optimal string matching
• Average running time of the Boyer-Moore-Horspool algorithm
• Fast average-case pattern matching by multiplexing sparse tables
• Fast two-dimensional pattern matching
• Constant-space string-matching in sublinear average time
• Speeding up two string-matching algorithms
• On Boyer-Moore automata
• Sublinear approximate string matching and biological applications
• Optimal pattern matching algorithms
• The wide window string matching algorithm
• Improved pattern-scan-order algorithms for string matching
• Geometry-based symbolic approximation for fast sequence matching on manifolds
• Average complexity of exact and approximate multiple string matching
• Efficient online string matching based on characters distance text sampling
• Towards optimal packed string matching
• Sequential and indexed two-dimensional combinatorial template matching allowing rotations
• On the average-case complexity of pattern matching with wildcards
• Improved characters distance sampling for online and offline text searching
• Fast string matching in stationary ergodic sources
• A very fast string matching algorithm based on condensed alphabets
• Worst case efficient single and multiple string matching in the RAM model
• DYNAMIC ALLOCATION OF FINITE AUTOMATA STATES FOR FAST STRING RECOGNITION
• FLEXIBLE MUSIC RETRIEVAL IN SUBLINEAR TIME
• ON IMPLEMENTATION AND PERFORMANCE OF TABLE-DRIVEN DFA-BASED STRING PROCESSORS
• Efficient variants of the backward-oracle-matching algorithm
• Fast and flexible packed string matching
• Improved and self-tuned occurrence heuristics
• String matching with alphabet sampling
• Average complexity of backward \(q\)-gram string matching algorithms
• Worst-case efficient single and multiple string matching on packed texts in the word-RAM model
• Linear and efficient string matching algorithms based on weak factor recognition
• On the decision tree complexity of string matching
• Fast algorithms for two dimensional and multiple pattern matching
• Speeding up two string-matching algorithms
• Designing optimal- and fast-on-average pattern matching algorithms
• Quantum pattern matching fast on average
• Fast Average-Case Pattern Matching on Weighted Sequences
• Efficient parameterized string matching

This page was built for publication: The Complexity of Pattern Matching for a Random String

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