Brute-force substring search

Cost and properties

typical	~n character compares
worst case	~m·n
backup	yes — i jumps back
space	O(1)

Reference: Sedgewick & Wayne, §5.3.

Brute-force substring search in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

def search(pat, txt):
    # Try every alignment i, comparing pattern characters left to right.
    m, n = len(pat), len(txt)
    for i in range(n - m + 1):
        j = 0
        while j < m and txt[i + j] == pat[j]:
            j += 1
        if j == m:
            return i                      # all m characters matched
    return n                              # no match: return the length

Why it works

Where the cost hides

On ordinary text a mismatch usually comes on the first character, so the scan is about n compares and nothing beats it for simplicity. The worst case is different: with aaaaab against a long run of a's, each alignment matches m−1 characters before failing — ~m·n compares. That pattern is not contrived; it is what binary data and DNA look like.

The backup problem

Watch i in the frames: after a mismatch, the next alignment re-reads text characters that were already examined. That is backup, and it is the real objection — not just the compare count. If the text arrives as a stream (a network socket, a huge file, a tape), you cannot rewind it, and an algorithm that needs to is unusable.

What the alternatives change

• KMP never backs up: it precomputes what state a mismatch leaves you in. Linear, guaranteed.
• Boyer–Moore scans the pattern backwards and skips forward in leaps, sublinear on typical text.
• Rabin–Karp compares hashes instead of characters, extending to 2-D and multiple patterns.

The rest of this lecture is three different answers to the one problem you can see here.

What to try in the animation

The worst case preset shows the pathology: almost the whole pattern matches at every alignment, so the scan re-reads the same characters over and over.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• course example — text: abacadabrabracabracadabrabrabracad · pattern: abracadabra
• worst case — text: aaaaaaaaaaaaaaaaaaaaab · pattern: aaaaab
• match at the start — text: needle in a haystack · pattern: needle
• no match — text: abcdefghijklmnop · pattern: xyz

Open Brute-force substring search in the player →

The rest of Substring search

• Knuth–Morris–Pratt Precompute, for every state and character, where a mismatch leaves you.
• Boyer–Moore Compare the pattern right to left. A mismatched text character that does not occur in the…
• Rabin–Karp Hash the pattern once, then hash every window of the text — each in constant time from…