Tighter lower bounds on the exact complexity of string matching

Richard Cole, Ramesh Hariharan, Mike Paterson, Uri Zwick

Research output: Contribution to journalArticle

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 + 9 ÷ 4(m + 1)) · n character comparisons is obtained. For general algorithms, a lower bound of about (1 + 2 ÷ m + 3) · n character comparisons is obtained. These lower bounds complement an on-line upper bound of about (1 + 8 ÷ 3(m + 1)) · 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.

Original languageEnglish (US)
Pages (from-to)30-45
Number of pages16
JournalSIAM Journal on Computing
Volume24
Issue number1
DOIs
StatePublished - 1995

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Tighter lower bounds on the exact complexity of string matching'. Together they form a unique fingerprint.

  • Cite this