On the Exact Complexity of String Matching: Lower Bounds

DOI10.1137/0220063zbMath0738.68042OpenAlexW1988753117MaRDI QIDQ3985805

Zvi Galil, Raffaele 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 searchingworst case behaviourtext editing

Mathematics Subject Classification ID

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

Related Items (6)

On a conjecture on bidimensional words. ⋮ Light-based string matching ⋮ Saving comparisons in the Crochemore-Perrin string-matching algorithm ⋮ A simple fast hybrid pattern-matching algorithm ⋮ On Simon's string searching algorithm ⋮ Tight comparison bounds for the string prefix-matching problem

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