Tighter upper bounds on the exact complexity of string matching

Richard Cole, Ramesh Hariharan

Research output: Contribution to journalArticlepeer-review


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 + 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 + 16/7m+27(n - m) character comparisons for m = 16k + 19, for any integer k ≥ 1, and for general algorithms is n + 2/m+3 (n - m) character comparisons, for m = 2k + 1, for any integer k ≥ 1.

Original languageEnglish (US)
Pages (from-to)803-856
Number of pages54
JournalSIAM Journal on Computing
Issue number3
StatePublished - Jun 1997


  • Comparisons
  • Exact complexity
  • Periodicity
  • String matching

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


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

Cite this