Tighter Upper Bounds on the Exact Complexity of String Matching

DOI10.1137/S009753979324694XMaRDI QIDQ4340774zbMATH OpenOpenAlexFDO

Authors Ramesh Hariharan, Richard Cole

Publication date 12 June 1997

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

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

zbMATH Keywords

comparisonsexact complexityonline algorithmsperiodicitystring 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

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

Cited in

(9)

• Improved pattern-scan-order algorithms for string matching
• Fast string matching for DNA sequences
• On the Exact Complexity of String Matching: Lower Bounds
• On the Exact Complexity of String Matching: Upper Bounds
• scientific article; zbMATH DE number 1256698 (Why is no real title available?)
• Tighter Lower Bounds on the Exact Complexity of String Matching
• Asymptotic Optimality of Antidictionary Codes
• \(k\) one-way heads cannot do string-matching
• Tight comparison bounds for the string prefix-matching problem

This page was built for publication: Tighter Upper 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 Q4340774)