On the exact complexity of string matching

The maximal number of character comparisons made by a linear-time string matching algorithm, given a text string of length n and a pattern string of length m over a general alphabet, is investigated. The number is denoted by c(n,m) or approximated by (1+C)n, where C is a universal constant. The subscript `online´ is added when attention is restricted to online algorithms, and the superscript `1´ is added when algorithms that find only one occurrence of the pattern in the text are considered. It is well known that n⩽c(n, m)⩽2n-m+1 or 0⩽C⩽1. These bounds are improved, and C_online is determined exactly