Tighter Upper Bounds on the Exact Complexity of String Matching
Richard Cole, Ramesh Hariharan · SIAM Journal on Computing · 1997
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 of n + O(n/m) character comparisons, following preprocessing. Specifically, we show an upper bound of $n + \frac{8}{3(m+1)}(n-m)$ character comparisons. This bound is achieved by an online algorithm which performs O(n) work in total and requires O(m) space and O(m2) time for preprocessing. The current best lower bound for online algorithms is $n + \frac{16}{7m+27}(n-m)$ character comparisons for $m=16k+19$, for any integer $k\geq 1$, and for general algorithms is $n+\frac{2}{m+3}(n-m)$ character comparisons, for $m=2k+1$, for any integer $k\geq 1$.