The Complexity of Pattern Matching for a Random String
From MaRDI portal
Publication:3854624
DOI10.1137/0208029zbMath0421.68045MaRDI QIDQ3854624
Publication date: 1979
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/9cefac9f2bcc75cd36702fe01476d469a51f9a66
68Q25: Analysis of algorithms and problem complexity
Related Items
Linear and Efficient String Matching Algorithms Based on Weak Factor Recognition, Unnamed Item, Speeding up two string-matching algorithms, Fast algorithms for two dimensional and multiple pattern matching, Fast Average-Case Pattern Matching on Weighted Sequences, 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, Designing optimal- and fast-on-average pattern matching algorithms, Quantum pattern matching fast on average, Efficient parameterized string matching, 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
