On the Exact Complexity of String Matching: Lower Bounds
Zvi Galil, Raffaele Giancarlo · SIAM Journal on Computing · 1991
This paper provides several lower bounds on the number of character comparisons that any string matching algorithm must perform in the worst case in order to find occurrences of a pattern string in a text string. The class of algorithms that are considered need not know the alphabet.