Tighter Lower Bounds on the Exact Complexity of String Matching

DOI10.1137/S0097539793245829MaRDI QIDQ4326851zbMATH OpenOpenAlexFDO

Authors Ramesh Hariharan, Uri Zwick, Richard Cole, Mike Paterson

Publication date 27 March 1995

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

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

zbMATH Keywords

lower boundspattern matchingstring matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Computing methodologies for text processing; mathematical typography (68U15)

Recommendations

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

Cited in

(15)

• Efficient comparison based string matching
• The complexity of mean payoff games on graphs
• Lower bounds of temporal and spatial complexity of the substring search problem
• On the Exact Complexity of String Matching: Lower Bounds
• On the Exact Complexity of String Matching: Upper Bounds
• On the Comparison Complexity of the String Prefix-Matching Problem
• scientific article; zbMATH DE number 1256698 (Why is no real title available?)
• Tighter Upper Bounds on the Exact Complexity of String Matching
• On the lower bound for parallel string matching
• scientific article; zbMATH DE number 5790350 (Why is no real title available?)
• The complexity of mean payoff games
• Tight comparison bounds for the string prefix-matching problem
• Fair quantitative games
• Light-based string matching
• A simple fast hybrid pattern-matching algorithm

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

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