The authors examine the problem of determining lower bounds on the number of string comparisons that must be performed in order to determine whether an m -character pattern p is present in an n -character text t, where n ≥ m . The alphabet on which the string comparisons are based has at least three characters. Binary alphabets are special cases and are not considered. The paper makes no presumption of specific algorithms by which the string comparisons are performed except that comparisons among individual characters in the text and pattern strings are performed.

The paper proves a number of theorems and lemmas that treat the following three cases:

• The general online case, in which the original text is tested in a moving m -character window for as many occurrences as may be present.

• The online case, in which the first occurrence of the pattern is sought. The searching ceases if a match is made.

• The offline case, in which the entire n -character text is tested with the pattern to find all occurrences of the pattern.

Somewhat different values for the lower bounds are found for these cases, depending on the number of characters in the pattern and whether the number is even or odd. The paper reports an approximate lower bound of 4 n &slash; 3 that is a conservative estimate applicable to all three cases.