On improving the worst case running time of the Boyer-Moore string matching algorithm

DOI10.1145/359146.359148zbMath0413.68041DBLPjournals/cacm/Galil79OpenAlexW1973272384WikidataQ56390278 ScholiaQ56390278MaRDI QIDQ3048242

Zvi Galil

Publication date: 1979

Published in: Communications of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/359146.359148

zbMATH Keywords

computational complexityworst case running timeBoyer-Moore string matching algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Related Items (19)

Tight bounds on the complexity of the Apostolico-Giancarlo algorithm ⋮ Speeding up two string-matching algorithms ⋮ On Boyer-Moore automata ⋮ Set intersection and sequence matching with mismatch counting ⋮ A unifying look at the Apostolico--Giancarlo string-matching algorithm ⋮ A simple fast hybrid pattern-matching algorithm ⋮ On-line string matching algorithms: survey and experimental results ⋮ A faster quick search algorithm ⋮ Parallel String Matching Algorithms ⋮ On the string matching with \(k\) mismatches ⋮ Periodicity and repetitions in parameterized strings ⋮ A variation on the Boyer-Moore algorithm ⋮ Complexity of substring search in a set of strings ⋮ On the size of Boyer-Moore automata ⋮ A New String Matching Algorithm ⋮ Speeding up two string-matching algorithms ⋮ Constant-space string-matching in sublinear average time ⋮ Time-space-optimal string matching ⋮ Periodicity and Repetitions in Parameterized Strings

This page was built for publication: On improving the worst case running time of the Boyer-Moore string matching algorithm