If you're looking for "aaaaaaaaaaaaaaaa" (that's a string of length 16) and you look in index 15 (counting from 0) and find a non-"a" there, you can leap forward 15 (or 16 - there's an off-by-one error waiting to bite) places. If that's also not an "a" then you can do it again.
It's more complex than that, but the complexity can, in some cases, be sub-linear.
There's another reference I have somewhere to a surprising (and contentious) sub-linear algorithm for something that's "obviously provably linear". I'll see if I can dig it up and post it later. No time now.
ADDED IN EDIT (because there's more than one reply saying the same thing)
Yes, it's futzing the constant. The point is that the constant can be less than one, it's not always necessary to examine every character in the string being searched, which comes as a surprise. But no, this is not sub-linear, although many people describe it as such. Knowing why it's not sub-linear, even when the constant is less than one, is an important milestone in learning about complexity of functions.