On the Exact Complexity of String Matching: Lower Bounds

DOI10.1137/0220063MaRDI QIDQ3985805zbMATH OpenOpenAlexFDO

Authors Zvi Galil, R. Giancarlo

Publication date 27 June 1992

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

Full work available at URL https://doi.org/10.1137/0220063

zbMATH Keywords

string matchingstring searchingtext editingworst case behaviour

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies for text processing; mathematical typography (68U15) Parallel algorithms in computer science (68W10)

Recommendations

• Tighter Lower Bounds on the Exact Complexity of String Matching
• Tighter Upper Bounds on the Exact Complexity of String Matching
• Exact bounds on the complexity of sequential string matching algorithms
• On the Exact Complexity of String Matching: Upper Bounds

Cited in

(21)

• Exact bounds on the complexity of sequential string matching algorithms
• Saving comparisons in the Crochemore-Perrin string-matching algorithm
• On a conjecture on bidimensional words.
• Lower bounds of temporal and spatial complexity of the substring search problem
• Tight bounds on the complexity of the Apostolico-Giancarlo algorithm
• The exact online string matching problem: a review of the most recent results
• scientific article; zbMATH DE number 1256698 (Why is no real title available?)
• Tighter Lower Bounds on the Exact Complexity of String Matching
• On the lower bound for parallel string matching
• Tighter Upper Bounds on the Exact Complexity of String Matching
• Average complexity of backward \(q\)-gram string matching algorithms
• On the lower bound for parallel string matching
• scientific article; zbMATH DE number 5790350 (Why is no real title available?)
• On the decision tree complexity of string matching
• scientific article; zbMATH DE number 7651042 (Why is no real title available?)
• \(k\) one-way heads cannot do string-matching
• On Simon's string searching algorithm
• Tight comparison bounds for the string prefix-matching problem
• The string guessing problem as a method to prove lower bounds on the advice complexity
• Light-based string matching
• A simple fast hybrid pattern-matching algorithm

This page was built for publication: On the Exact Complexity of String Matching: Lower Bounds

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