The Complexity of Pattern Matching for a Random String

DOI10.1137/0208029zbMath0421.68045OpenAlexW2071461587MaRDI QIDQ3854624

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

string matchingaverage case complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Speeding up two string-matching algorithms, On Boyer-Moore automata, Sublinear approximate string matching and biological applications, Average complexity of exact and approximate multiple string matching, Fast algorithms for two dimensional and multiple pattern matching, Efficient parameterized string matching, On the average-case complexity of pattern matching with wildcards, Fast and flexible packed string matching, Improved and self-tuned occurrence heuristics, Improved characters distance sampling for online and offline text searching, String matching with alphabet sampling, Unnamed Item, Average complexity of backward \(q\)-gram string matching algorithms, Efficient online string matching based on characters distance text sampling, Towards optimal packed string matching, Worst-case efficient single and multiple string matching on packed texts in the word-RAM model, ON IMPLEMENTATION AND PERFORMANCE OF TABLE-DRIVEN DFA-BASED STRING PROCESSORS, Fast Average-Case Pattern Matching on Weighted Sequences, Linear and Efficient String Matching Algorithms Based on Weak Factor Recognition, Optimal pattern matching algorithms, Worst Case Efficient Single and Multiple String Matching in the RAM Model, Average running time of the Boyer-Moore-Horspool algorithm, Fast average-case pattern matching by multiplexing sparse tables, Designing optimal- and fast-on-average pattern matching algorithms, Quantum pattern matching fast on average, Fast two-dimensional pattern matching, The wide window string matching algorithm, Fast String Matching in Stationary Ergodic Sources, Improved pattern-scan-order algorithms for string matching, Geometry-based symbolic approximation for fast sequence matching on manifolds, A Very Fast String Matching Algorithm Based on Condensed Alphabets, Speeding up two string-matching algorithms, EFFICIENT VARIANTS OF THE BACKWARD-ORACLE-MATCHING ALGORITHM, Constant-space string-matching in sublinear average time, Average-optimal string matching, DYNAMIC ALLOCATION OF FINITE AUTOMATA STATES FOR FAST STRING RECOGNITION, FLEXIBLE MUSIC RETRIEVAL IN SUBLINEAR TIME, Sequential and indexed two-dimensional combinatorial template matching allowing rotations