Tighter Lower Bounds on the Exact Complexity of String Matching

DOI10.1137/S0097539793245829zbMath0828.68100OpenAlexW2155912811MaRDI QIDQ4326851

Ramesh Hariharan, Uri Zwick, Richard John Cole, Mike S. 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 boundsstring matchingpattern matching

Mathematics Subject Classification ID

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

Related Items (4)

Light-based string matching ⋮ The complexity of mean payoff games on graphs ⋮ The complexity of mean payoff games ⋮ A simple fast hybrid pattern-matching algorithm

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