AlgoVerse

Naive string matching

Put the pattern under every possible position of the text and compare character by character; simple, but O((n − m + 1)·m) in the worst case.

We want every place where the pattern P (of length m) occurs in the text T (of length n). The simplest method: put the pattern under every shift s = 0 … n − m and compare left to right until the characters differ.

Read the full explanation ↓
Input:
T="acaabcabaaba…" · P="abaa"PDF export

The pattern abaa occurs once in the text acaabcabaabac, at shift 6; every shift is tried on its own.

  1. def naive_match(T, P):
  2. n, m = len(T), len(P)
  3. matches = []
  4. for s in range(n - m + 1):
  5. q = 0
  6. while q < m and T[s + q] == P[q]:
  7. q = q + 1
  8. if q == m:
  9. matches.append(s)
  10. return matches

Invariant: Every occurrence of P that starts before shift s is in matches.

Start

0123456789101112
acaabcabaabac
abaa
matches—

Local variables

T'acaabcabaabac'
P'abaa'

Orange = changed in this step

Call stack

  1. naive_match()line 1
Step 1 of 70
Black = shift · Orange = key stepshift: 0/10 · equal: 0/12 · found: 0/1
    Explanation

    The idea

    We want every place where the pattern P (of length m) occurs in the text T (of length n). The simplest method: put the pattern under every shift s = 0 … n − m and compare left to right until the characters differ.

    Cost

    In the worst case (like aaa…ab) almost m comparisons are needed at every shift: O((n − m + 1)·m). The trouble is that what earlier comparisons learned is thrown away; KMP keeps it and reaches O(n + m).

    What to watch in the trace

    • The pattern is drawn under the text at shift s; its filled cells have matched the text so far.