On Simon's string searching algorithm (Q685473)

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}.