On the Exact Complexity of String Matching: Upper Bounds

DOI10.1137/0221028zbMath0761.68046OpenAlexW4239658213MaRDI QIDQ4016906

Raffaele Giancarlo, Zvi Galil

Publication date: 16 January 1993

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

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

zbMATH Keywords

string matchingstring searchingworst case behaviortext 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 (9)

Light-based string matching ⋮ Saving comparisons in the Crochemore-Perrin string-matching algorithm ⋮ A simple fast hybrid pattern-matching algorithm ⋮ How the character comparison order shapes the shift function of on-line pattern matching algorithms ⋮ On Simon's string searching algorithm ⋮ Tight comparison bounds for the string prefix-matching problem ⋮ Improved pattern-scan-order algorithms for string matching ⋮ Fast string matching for DNA sequences ⋮ A New String Matching Algorithm

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