Exact bounds on the complexity of sequential string matching algorithms

zbMATHMaRDI QIDQ1326953FDO

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

zbMATH Keywords

computational complexityfinite automatastring matchingstring searchingworst case behaviortext editing

Mathematics Subject Classification ID

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)

Recommendations

• On Simon's string searching algorithm
• Tight comparison bounds for the string prefix-matching problem
• On the Exact Complexity of String Matching: Upper Bounds
• Efficient comparison based string matching
• On the Exact Complexity of String Matching: Lower Bounds

Cited in

(15)

• String-matching cannot be done by a two-head one-way deterministic finite automaton
• scientific article; zbMATH DE number 1256698 (Why is no real title available?)
• Average complexity of backward \(q\)-gram string matching algorithms
• Tight comparison bounds for the string prefix-matching problem
• On the Exact Complexity of String Matching: Upper Bounds
• Tight bounds on the complexity of the Apostolico-Giancarlo algorithm
• String Processing and Information Retrieval
• Tighter Lower Bounds on the Exact Complexity of String Matching
• A Boyer-Moore type string matching algorithm with memory and its computational complexity
• The exact online string matching problem: a review of the most recent results
• Linear-Time Sequence Comparison Using Minimal Absent Words & Applications
• scientific article; zbMATH DE number 5790350 (Why is no real title available?)
• scientific article; zbMATH DE number 7651042 (Why is no real title available?)
• 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)