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) = (q (n - m{ m} + 2) ) if m n 2m, \ and \ c (, n) = ({ q m }mn) 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.