On Simon's string searching algorithm
type: Item
instance of: scholarly article
title: On Simon's string searching algorithm
zbMATH Open document ID: 0781.68068
DOI: 10.1016/0020-0190(93)90231-W
author: Christophe Hancart
published in: Information Processing Letters
publication date: 1993-10-17T00:00:00Z
review text: We give sharp bounds for the problem of string matching when only one head moving from the right to the left of the text is used: \((2-1/m)n\) character comparisons for all the text, and \(\min \{1+ \log_ 2m,\text{Card}(A)\}\) character comparisons on each character of the text, where \(m\) is the length of the pattern, \(n\) the length of the text, and \(A\) the alphabet. These bounds improve on the previous bounds given by \textit{D. E. Knuth}, \textit{J. H. Morris} and \textit{V. R. Pratt} [SIAM J. Computing 6, 323-350 (1977; Zbl 0372.68005)], and, more recently, by \textit{H.-J. Simon}.
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 417390
zbMATH Keywords: finite automata
zbMATH Keywords: string matching
MaRDI profile type: Publication
cites work: Q4773298
cites work: Q4228434
cites work: On the Exact Complexity of String Matching: Lower Bounds
cites work: On the Exact Complexity of String Matching: Upper Bounds
cites work: Fast Pattern Matching in Strings
cites work: Q3659988
cites work: Q4385527
full work available at URL: 0020-0190(93)90231-w
OpenAlex ID: W2074791768
description: scientific article; zbMATH DE number 417390