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

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).