On the exact complexity of string matching: lower bounds

摘要: It is shown that, for any pattern of length m and text n, it possible to find all occurrences the in overall linear time at most $\frac{4}{3}n - \frac{1}{3}m$ character comparisons. In fact, bound on number comparisons usually tighter than this, expressed terms structure pattern. The algorithm here need not have knowledge alphabet. This improves best previous $1.5n-.5(m 1)$ obtained by Colussi [Inform. Comput., appear] Apostolico Crochemore [Tech. Report TR89-75, LITP, Universite de Paris, France, 1989]. a companion paper [SIAM J. 20 (1991), pp. 1008–1020], authors show lower on-line algorithms that equal $m = 3$. For 1,2,n$ optimal. based new analysis string matching Colussi. Moreover, this Colussi’...