The Complexity of Pattern Matching for a Random String

We study the average-case complexity of finding all occurrences of a given pattern α in an input text string. Over an alphabet of q symbols, let c(α ,n) be the minimum average number of characters that need to be examined in a random text string of length n. We prove that, for large m, almost all patterns α of length m satisfy \[ c(α ,n) = θ ( log _q ({{n - m}}{{ln m}} + 2) ) if m n 2m, \] and \[ c(α ,n) = θ ( {{ {log _q m} }}{m}n ){if } n > 2m. \] This in particular confirms a conjecture raised in a recent paper by Knuth, Morris, and Pratt (Fast pattern matching in strings, SIAM J. Comput., 6 (1977), pp. 323–350.