Cole, Richard ; Hariharan, Ramesh ; Paterson, Mike ; Zwick, Uri
(1995)
*Tighter lower bounds on the exact complexity of string matching*
SIAM Journal on Computing, 24
(1).
pp. 30-45.
ISSN 0097-5397

Full text not available from this repository.

Official URL: http://epubs.siam.org/doi/abs/10.1137/S00975397932...

Related URL: http://dx.doi.org/10.1137/S0097539793245829

## Abstract

This paper considers the exact number of character comparisons needed to find all occurrences of a pattern of length m in a text of length n using on-line and general algorithms. For on-line algorithms, a lower bound of about $(1 + \frac{9}{4(m + 1)}) \cdot n$ character comparisons is obtained. For general algorithms, a lower bound of about $(1 + \frac{2}{m + 3}) \cdot n$ character comparisons is obtained. These lower bounds complement an on-line upper bound of about $(1 + \frac{8}{3(m + 1)}) \cdot n$ comparisons obtained recently by Cole and Hariharan. The lower bounds are obtained by finding patterns with interesting combinatorial properties. It is also shown that for some patterns off-line algorithms can be more efficient than on-line algorithms.

Item Type: | Article |
---|---|

Source: | Copyright of this article belongs to Society for Industrial and Applied Mathematics. |

ID Code: | 102265 |

Deposited On: | 09 Mar 2018 11:23 |

Last Modified: | 09 Mar 2018 11:23 |

Repository Staff Only: item control page