Exact bounds on the complexity of sequential string matching algorithms
zbMATH Open0803.68039MaRDI QIDQ1326953FDOQ1326953
Authors: Christophe Hancart 
Publication date: 2 January 1995
Published in: Bulletin of the Belgian Mathematical Society - Simon Stevin (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/223646
Recommendations
computational complexityfinite automatastring matchingstring searchingworst case behaviortext editing
Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Parallel algorithms in computer science (68W10) Computing methodologies for text processing; mathematical typography (68U15)
Cited In (15)
- On the Exact Complexity of String Matching: Upper Bounds
- String-matching cannot be done by a two-head one-way deterministic finite automaton
- Tight comparison bounds for the string prefix-matching problem
- Linear-Time Sequence Comparison Using Minimal Absent Words & Applications
- A Boyer-Moore type string matching algorithm with memory and its computational complexity
- Tight bounds on the complexity of the Apostolico-Giancarlo algorithm
- Average complexity of backward \(q\)-gram string matching algorithms
- The exact online string matching problem: a review of the most recent results
- String Processing and Information Retrieval
- Title not available (Why is that?)
- Tighter Lower Bounds on the Exact Complexity of String Matching
- Title not available (Why is that?)
- Title not available (Why is that?)
- On Simon's string searching algorithm
- On the complexity of learning strings and sequences
This page was built for publication: Exact bounds on the complexity of sequential string matching algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1326953)
