R. Cole and R. Hariharan

SIAM Journal on Computing, 26(1997), 803-856.

This paper considers how many character comparisons are needed to find all occurrences of a pattern of length m in a text of length n. The main contribution is to show an upper bound of the form n+O(n/m) character comparisons, following preprocessing. Specifically, we show an upper bound of n + (8/(3(m+1))).(n-m) character comparisons. This bound is achieved by an online algorithm which performs O(n) work in total, requires O(m) space and O(m^2) time for preprocessing. The current best lower bound for online algorithms is n + 16/(7m+27)).(n-m) character comparisons for m=16k+19, for any integer k >= 1, and for general algorithms is n+2(n-m)/(m+3) character comparisons, for m=2k+1, for any integer k >= 1.

postscript of full paper