KMP always looks at every position, but it is linear.
There is a variant of Boyer Moore which is sublinear and linear in the worst case, but it's not that fast by modern standards.
The fastest sub linear search algorithms I know that remain linear in the worst case are Linear Weak Factor Recognition (LWFR) and Linear Hash Chain (LHC). LHC is currently unpublished (I'm writing a paper on it right now).
There is a variant of Boyer Moore which is sublinear and linear in the worst case, but it's not that fast by modern standards.
The fastest sub linear search algorithms I know that remain linear in the worst case are Linear Weak Factor Recognition (LWFR) and Linear Hash Chain (LHC). LHC is currently unpublished (I'm writing a paper on it right now).