A Correct Preprocessing Algorithm for Boyer–Moore String-Searching

DOI10.1137/0209037zbMath0446.68049OpenAlexW1984074972MaRDI QIDQ3891776

Wojciech Rytter

Publication date: 1980

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

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

zbMATH Keywords

algorithmpattern matchingBoyer-Moore string-searchingtable of pattern shifts

Mathematics Subject Classification ID

Searching and sorting (68P10) Information storage and retrieval of data (68P20)

Related Items (10)

Tight bounds on the complexity of the Apostolico-Giancarlo algorithm ⋮ Speeding up two string-matching algorithms ⋮ A Heuristic For Computing Repeats With A Factor Oracle: Application To Biological Sequences ⋮ Fast algorithms for two dimensional and multiple pattern matching ⋮ A unifying look at the Apostolico--Giancarlo string-matching algorithm ⋮ A variation on the Boyer-Moore algorithm ⋮ Unnamed Item ⋮ Speeding up two string-matching algorithms ⋮ Correctness of substring-preprocessing in Boyer-Moore's pattern matching algorithm ⋮ A complete mechanization of correctness of a string-preprocessing algorithm

This page was built for publication: A Correct Preprocessing Algorithm for Boyer–Moore String-Searching