Naive substring search shifts the pattern by one position after a mismatch and compares everything again, so in the worst case it does O(n·m) work. The Knuth–Morris–Pratt (KMP) algorithm never goes back in the text: it first analyses the pattern and then scans the text once, in O(n + m). A different approach to the same problem is Rabin–Karp.

The lps table of the pattern ababaca
The lps table of the pattern ababaca

The problem with naive search

On the text a × 1000 and the pattern a × 50 + b the naive algorithm checks almost the whole pattern at each of 950 starts.

python
def naive_count(text, pat):
    cmp = 0
    for i in range(len(text) - len(pat) + 1):
        for j in range(len(pat)):
            cmp += 1
            if text[i + j] != pat[j]:
                break
    return cmp

text = "a" * 1000
pat = "a" * 50 + "b"
print(naive_count(text, pat))
text
48450

The prefix function (lps)

lps[i] is the length of the longest proper prefix of p[0..i] that is also a suffix of it. For ababaca the table is [0, 0, 1, 2, 3, 0, 1]. It tells us how many matched letters can be kept after a mismatch.