@Article{Riv77c,
  author = 	 { Ronald L. Rivest },
  title = 	 { On the worst-case behavior of string-searching algorithms },
  journal = 	 { SIAM J. Computing },
  OPTyear = 	 { 1977 },
  OPTmonth = 	 { December },
  date =         { 1977-12 },                  
  volume = 	 { 6 },
  number = 	 { 4 },
  pages = 	 { 669--674 },
  publisher =    { SIAM },                   
  url =          { http://link.aip.org/link/?SMJ/6/669/1 },
  doi =          { 10.1137/0206048 },
  keywords =     { string-searching; pattern matching; text editing; computational complexity; worst-case behavior },
  abstract =     {
                   Any algorithm for finding a pattern of length $k$ in a string
                   of length $n$ must examine at least $n-k+1$ of the characters
                   of the string in the worst case.  By considering the pattern
                   00\cdots0, we prove that this is the best possible result. 
                   Therefore there do not exist pattern matching algorithms whose
                   worst-case behavior is ``sublinear'' in $n$ (that is, linear
                   with constant less than one), in contrast with the situation
                   for average behavior (the Boyer-Moore algorithm is known to be
                   sublinear on the average).                  
                 },
}