TIGHTER LOWER BOUNDS ON THE EXACT COMPLEXITY OF STRING-MATCHING

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 compa risons is obtained. These lower bounds complement an on-line upper bou nd of about (1+8/3(m+1)).n comparisons obtained recently by Cole and H ariharan. The lower bounds are obtained by finding patterns with inter esting combinatorial properties. It is also shown that for some patter ns off-line algorithms can be more efficient than on-line algorithms.