Answers are grounded in this paper and cite their sources.
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<or=c(n,m)<or=2n-m+1 or 0<or=C<or=1. These bounds are improved, and C/sub online/ is determined exactly.<<ETX>>
No takes yet. Share an insight, caveat, or question.
Colussi et al. (2002) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: