Naive matching

Finding a word inside a longer text is one of the oldest jobs a computer does: a search box, a virus scanner, a DNA lab. This lesson starts with the simplest method, counts what it costs, and points at the information it throws away. The next three lessons use that information.

Text, pattern and places

The text T is the long string we search in, with n letters. The pattern P is the string we look for, with m letters, and m ≤ n. P occurs at place i when T[i:i+m] == P: the m letters of T starting at place i are exactly P. In the figures, the row T is the text and the row P is the pattern.

There are n − m + 1 places where P could start: 0, 1, …, n − m. At a later place P would stick out past the end of T. Occurrences can overlap: in "aaaa", the pattern "aa" occurs at places 0, 1 and 2.

ARRS-6 met this search as p in t and t.find(p). This station looks at how such a search works inside, and at methods whose cost is guaranteed.

Try every place

The naive method tries every place in turn. At each place it compares P with T letter by letter from the left, and stops at the first pair that differs. If all m pairs are equal, it reports the place.

def find_all(t, p):
    n, m = len(t), len(p)
    found = []
    for i in range(n - m + 1):        # every place P could start
        j = 0
        while j < m and t[i + j] == p[j]:
            j += 1
        if j == m:                    # all m letters matched
            found.append(i)
    return found

Two details are easy to get wrong. The loop runs to n - m + 1, so the last place, n − m, is tried. And after a match P moves on by one place, not by m, so overlapping occurrences are found. Step through both variants of the figure.

What it costs

Each place costs at most m comparisons, so the whole search costs at most (n − m + 1) · m, which is O(n · m). The figure’s second variant reaches this bound: in "aaaaaaaa" every place matches "aaa" and fails on the last letter. With a text of a million letters and a pattern of a thousand, that is about a billion comparisons.

On ordinary text the naive method is much better than its bound. If the letters were random, picked from an alphabet of σ letters (σ is the Greek letter sigma), the first comparison at a place fails with chance 1 − 1/σ, the second is reached with chance 1/σ, the third with chance 1/σ² (σ² is σ times σ), and so on. The expected comparisons per place are 1 + 1/σ + 1/σ² + … < σ/(σ − 1), which is less than 2 for every alphabet of two or more letters. So on random text the naive search costs O(n). The trouble is text that is not random: long runs of one letter, repeated blocks in DNA, or input chosen by someone who wants your program to be slow.

What the naive method forgets

Look at place 0 of the worst case. The method compared T[0..2] with "aaa" and they matched. Then it moved to place 1 and compared T[1] and T[2] again, though it already knew both were "a".

That knowledge comes from the pattern alone, so it can be worked out before the search starts. If the text never has to be read twice, the search costs O(n + m). There are two classic ways to use this:

• KMP (lesson 2) works out, for every j, how far P can slide after a mismatch without missing an occurrence.
• The Z-algorithm (lesson 3) works out, for every place, how long a start of P begins there.

A third way, the rolling hash (lesson 4), avoids comparing letters at most places at all.

Python’s own tools

t = "abcabcab"
"cab" in t              # True
t.find("cab")           # 2: the first place, or -1
t.find("cab", 3)        # 5: the first place from 3 on
t.index("xyz")          # ValueError instead of -1
t.count("aa")           # counts without overlap: "aaaa".count("aa") is 2

import re
[m.start() for m in re.finditer("(?=aa)", "aaaa")]   # [0, 1, 2]

• in, find, index and count run in C, so they are much faster than a Python loop. CPython mixes methods: for short patterns a fast form of Boyer–Moore–Horspool, and since Python 3.10, for long patterns, the two-way method of Crochemore and Perrin, which is O(n + m) in the worst case.
• count does not count overlapping occurrences. To find every place, call find again from one place after the last hit, or use re.finditer with a lookahead, (?=…), which matches without using up any letters.
• In a regular expression, . matches any one character. So re.finditer("(?=c.b)", t) finds “c, any letter, b” at every place. Regular expressions can also be very slow on some patterns, because Python’s re tries the choices one after another.

One call of find is fast. A loop of calls can still be slow: if P occurs at almost every place of T, each call checks all m letters again. Lesson 2’s practice problem has exactly such a test.

Now try STRG-P1, Patterns with blanks.