I looked at that Wikipedia link myself. I can't remember exactly how it works.
The time complexity is linear because the algorithm records where a discrepancy occurred. It is then not necessary to start searching where we left off, but to start beyond the first error. If you started one character on from the previous unsuccessful search, in the worst‑case scenario which Wikipedia describes as finding a match for AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...AAAAAAAAAAAB, it is possible to start from a later place, possibly beyond the B. That runs in
n×
m time complexity.
The best‑case scenario is that the
String sought is a very short prefix of the longer String, in which case it will tend towards constant time. But that isn't going to happen in real life, is it?