Naive substring search in Python

Why it matters

Finding a word inside a text is one of the most common jobs a program does. A text editor's Find box does it. A search engine checks whether a page contains a phrase. A log reader looks for the line that says ERROR. A compiler looks for the keyword class in a source file. In each case the program has a long text and a shorter piece to look for, which is called the pattern. The program must answer one question: where does the pattern first appear in the text, or does it appear at all?

The simplest method is to try every starting position in the text and check whether the pattern matches there. This is the naive method. It is easy to write and easy to check by hand. It also has a cost that grows quickly with the size of the input, and understanding that cost is the main goal of this lesson.

The CSV lesson before this one split a line at commas. That job looked at each character once. Substring search is different, because the same characters of the text can be checked many times, once for each place where the pattern might start.

The problem in plain words

Let the text have n characters and the pattern have m characters. A substring is a run of characters that sits next to each other inside a longer string. The pattern is a substring of the text if the text contains exactly the same characters, in the same order, somewhere inside it.

The search returns the index of the first match. An index is a position number, counted from 0 at the first character. The first character of "the cat" is at index 0, the c is at index 4, and the t is at index 6. If there is no match, the search returns -1. The value -1 is a standard way to say "not found", because no real index can be negative.

Here is a small example. The text is the cat sat on the mat, and the pattern is the. The word the appears at index 0 and again at index 15. The first answer is 0.

The idea: slide and compare

Imagine writing the pattern on a strip of paper and laying it under the text, starting at the first character. Compare the strip with the text from left to right. If every letter matches, you have found the pattern. If one letter differs, slide the strip one step to the right and start comparing again from its first letter.

The strip is laid at each possible starting position in turn. The last position where the pattern can fit is the position where its last character lines up with the last character of the text. For a text of length n and a pattern of length m, that last starting index is n - m. Every starting index from 0 up to n - m must be tried, and no others.

In code, the idea is two nested loops. The outer loop moves the strip. The inner loop compares one character at a time:

for start in range(n - m + 1):
    # compare the pattern with the text at position start
    pass

The range(n - m + 1) call gives the numbers from 0 up to n - m, which is exactly the set of starting positions. The inner loop compares characters one at a time. As soon as one character differs, the inner loop stops, because this starting position cannot be a match. The outer loop then moves to the next starting position.

The naive search in Python

Here is the search with a counter added. The counter records every character comparison, so you can see the cost in numbers. The function returns both the index and the count.

The output is:

(0, 3)

The variable j counts how many characters of the pattern matched at the current start. If j reaches m, every character matched, and the function returns start right away. If the inner loop stops early, j is smaller than m, and the outer loop moves on. After the outer loop finishes without a match, the function returns -1.

Two details matter. The outer loop stops at n - m, not at n. If it went past that point, text[start + j] would ask for a character that is not in the text, and Python would raise IndexError. The inner loop reads text[start + j] and pattern[j], so the text index is always the start plus the offset inside the pattern.

Worked example 1: find "the" in a sentence

Take the text the cat sat on the mat and the pattern the. The text has 22 characters, so n is 22. The pattern has 3 characters, so m is 3. The outer loop tries starts from 0 to 19, which is n - m.

At start 0, the characters t, h, e in the text match the pattern exactly, so the search returns 0 at once. The first match is found right away, with only three comparisons, which is the (0, 3) in the output.

Worked example 2: a search that compares several times

The pattern ana in the text banana shows what happens when a start position fails after some matching characters. Here is the trace, with the counter in place:

The output is:

found at 1 after 4 comparisons

The trace goes like this.

• Start 0: the text character b is compared with the pattern character a. They differ, so the inner loop stops after 1 comparison.
• Start 1: a matches a, n matches n, and a matches a. The whole pattern matches after 3 comparisons. The search returns 1.

The total is 1 + 3 = 4. The start-0 attempt was cheap because the very first character failed. The start-1 attempt was the one that matched.

Now a case where a start fails after several matching characters. Take the text aaab and the pattern aab. At start 0, the text characters a, a match the pattern, and then a does not match b. That attempt costs 3 comparisons and fails. At start 1, the characters a, a, b all match, which costs 3 more comparisons. The search returns 1 after 6 comparisons in total. The start 0 attempt taught the search nothing about the start 1 attempt, so the naive method compares the same text characters again. That repeated work is the weakness this method is known for.

Worked example 3: find every match, including overlapping ones

The first match is only one part of a search. Many tasks need every position where the pattern appears. The function below collects all of them into a list. It uses the same idea of trying each start position, and it compares slices of the text, which is shorter to write:

The output is:

aaaa with aa: [0, 1, 2]
the cat sat on the mat with the: [0, 15]
mississippi with ssi: [2, 5]

The first line shows overlapping matches. The pattern aa appears at index 0, index 1 and index 2 of aaaa. The matches share characters, and that is correct. When the search moves forward by one position after each match, it finds all of them. A search that jumped past the whole match after each hit would find only the first and third. Decide what your task needs before you choose the step size.

The third line shows the same thing in a different word. mississippi contains ssi at index 2 and at index 5. The two matches do not overlap, but the naive method finds both anyway, because it checks every start position.

A slice such as text[start:start + m] makes a new string of length m at each start. That is an extra copy for each start, so this version does more copying than the loop in the earlier example, which compares characters in place. For short patterns the difference is small. The lesson of the slice version is that Python lets you write the comparison in one line, and you should know what it costs.

The str.count method does not solve this problem for overlapping matches. "aaaa".count("aa") returns 2, not 3, because count moves past each match after it finds it. The count of overlapping matches needs the loop above, or the trick with re.finditer in the next section.

Counting comparisons in the worst case

The worst case is the input that makes the search do the most work. For naive search, it is a text that matches the pattern almost everywhere, but fails at the last character every time.

Here is that input. The text is a repeated n times. The pattern is a repeated m - 1 times followed by a b. The text never contains a b, so the search never finds a match. At every start position, the inner loop matches the first m - 1 characters and then fails on the b. That costs m comparisons at each start.

The number of start positions is n - m + 1. Each start costs m comparisons. The total is:

comparisons = (n - m + 1) * m

The program below checks that formula on five input sizes:

The output is:

n=10 m=3 found=-1 comparisons=24 formula=24
n=20 m=3 found=-1 comparisons=54 formula=54
n=20 m=5 found=-1 comparisons=80 formula=80
n=100 m=10 found=-1 comparisons=910 formula=910
n=1000 m=10 found=-1 comparisons=9910 formula=9910

The counted number matches the formula in every row. Look at the last two rows. When the text grows ten times, from 100 to 1000, the comparisons grow about ten times as well (910 to 9910). The pattern length also matters. A pattern of length 10 costs about ten times as much as a pattern of length 1 on the same text.

If you multiply out the formula for large inputs, the expression is roughly n * m. Computer scientists write this as O(n * m). The letter O describes how the cost grows as the input grows, and it ignores fixed small costs. For a text of a million characters and a pattern of a hundred characters, the worst case is about a hundred million comparisons. In Python, each comparison is a loop step, which is slower than a comparison inside a built-in function. A program that does this for every line of a large file will feel slow.

A useful habit is to ask what the worst case looks like before you trust a search. A text full of repeated characters, such as a log file that repeats one line, is a common real case. The naive search handles normal text well, but it can be slow on text that is very repetitive.

Here is one more case where the search does real work before it finds the answer. The text is 20 a characters followed by a b, and the pattern is four a characters followed by a b:

The output is:

(16, 85)

The search tries starts 0 to 15 and fails each time. Each failure costs 5 comparisons, because the first four characters match and the fifth fails. That is 16 times 5, which is 80. The start 16 then matches all five characters, which adds 5 more. The total is 85.

Comparing with str.find and re

Python already has ways to search a string. You should know them, because real code should use a built-in method when one exists and does the job. The naive search in this lesson is for learning. The two built-in tools that matter here are the find method of str, and the re module, which searches with regular expressions.

str.find takes the pattern as plain text and returns the first index, or -1. It also takes a second argument, which is the index to start from:

The output is:

0
15
-1

str.find does not take a regular expression. The pattern is always read as plain characters, which is what a substring search means. If you want the regex meaning, use re.

The re module searches for a pattern written as a regular expression. A regular expression is a small language for describing text. In that language, a dot means "any single character", and a plus means "one or more of the character before it". To search for plain text with re, wrap the text with re.escape, which tells the engine to treat every character as an ordinary letter:

The output is:

0
None
True
False

re.search returns a match object, or None when the pattern is missing. The start() method of the match object gives its index. The function returns only the first match, so the line print(match.start() if match else -1) uses the same -1 rule as find.

The third line shows why re.escape matters. Without it, the dot in a.b means "any single character", so a.b matches axb as well. With re.escape, the dot is an ordinary dot, and axb does not match. A search meant for plain text needs the escape, or it can find matches you did not ask for.

To find every match, including overlapping ones, use re.finditer with a lookahead. A lookahead is a part of a regular expression that checks text ahead of the current position without consuming it, so the next search can start one step later:

The output is:

[0, 1, 2]
[2, 5]
2

The lookahead version finds the overlapping matches at 0, 1 and 2. The count method reports 2, because it does not count overlapping matches.

Here is a check that the naive method, find and re.search agree on several inputs. It uses re.escape as above:

The output is:

text="banana" pattern="ana" naive=1 find=1 re=1
text="aaaa" pattern="aa" naive=0 find=0 re=0
text="hello" pattern="xyz" naive=-1 find=-1 re=-1
text="abc" pattern="abc" naive=0 find=0 re=0
text="" pattern="a" naive=-1 find=-1 re=-1

All three methods return the same index on these inputs. They differ in what they cost and in what you can ask them. The naive method shows the steps. str.find is the choice for plain text in normal code. re is the choice when the pattern has rules, such as "a digit followed by a letter", which plain text cannot express.

This lesson does not measure how str.find is built inside CPython, the standard Python interpreter. The implementation uses a faster method than the naive loop in most cases. Do not assume its speed from this lesson. If speed matters for your input, measure it with your own data, using time.perf_counter().

Common mistakes

Off-by-one loop bound. A common error is writing the outer loop as range(n) instead of range(n - m + 1). The loop then tries starts where the pattern runs past the end of the text. With the text ba and the pattern ab, the loop reaches start 1, which matches a and then asks for the character at index 2. The text has only two characters, so Python raises an error:

IndexError: string index out of range

The same mistake with a pattern longer than the text fails in the same way. Calling the loop with the text abc and the pattern abcd reads index 3 of a three-character string, and Python raises the same IndexError.

The fix is the bound range(n - m + 1). With that bound, a pattern longer than the text makes the loop run zero times, and the function returns -1 with no error. The naive search gives -1 for abc and abcd, which is the correct answer. Note also that "abc".find("abcd") returns -1 directly, so the built-in method has no bound to get wrong.

Forgetting re.escape. A pattern with a dot, a plus, a bracket or a parenthesis means something special in a regular expression. A plain word that contains one of these characters will match the wrong text, or will fail to compile. Passing the raw pattern a(b to re.compile gives this error:

re.error: missing ), unterminated subpattern at position 1

The parenthesis starts a group that is never closed. The message names the position where the problem was found. The fix is re.escape("a(b"), which returns a\(b, and makes the search treat the parenthesis as a plain character. The rule is simple: use re.escape whenever the pattern comes from the user or from data, and str.find when you only need plain text.

Expecting the empty pattern to be missing. An empty pattern is a string of length zero. Both the naive method in this lesson and str.find return 0 for it, because the inner loop runs zero times and the first start matches. Python's "abc".find("") returns 0 too. If your code treats an empty pattern as a special case, decide what the answer should be and test it, rather than relying on the default.

Stopping at the first failed character too early. A search that gives up after one failed comparison at the first start, instead of moving to the next start, misses matches later in the text. The outer loop must try every start position. The inner loop is the part that stops early, and the outer loop is the part that keeps going.

Comparing with is. In Python, == compares the characters of two strings, so text[start:start + m] == pattern is correct. A learner from another background may reach for is by habit, which compares object identity instead. The same rule from the first lesson applies: use == for text, and is only for None.

Practice

1. Use the worst-case formula to find how many comparisons the naive search makes on the text aaaaaaa (7 characters) with the pattern aab. Then say what the search returns.

Show the answer

The formula is (n - m + 1) times m. Here n is 7 and m is 3, so the count is (7 - 3 + 1) times 3, which is 5 times 3, which is 15. The search returns -1, because the text has no b. Running the function on these inputs prints (-1, 15).

2. Write a function count_matches(text, pattern) that returns how many positions match, including overlapping ones. Use the find_all function from this lesson. Test it on aaaa and aa.

Show the answer

def count_matches(text, pattern):
    return len(find_all(text, pattern))
 
print(count_matches("aaaa", "aa"))

The output is 3. find_all returns [0, 1, 2] for these inputs, so the function returns 3. The matches at index 1 and 2 overlap with the match at index 0, and they are counted.

3. Predict the first index and the full list of matches for the text mississippi and the pattern ssi. Then check your answer by running find_all.

Show the answer

The first index is 2, and the full list is [2, 5]. The text has s at indexes 2, 3, 5 and 6, and ssi appears starting at 2 and at 5. Running find_all("mississippi", "ssi") prints [2, 5].

4. The text is abc and the pattern is abcd. Explain what the naive search returns and why the outer loop does not run any comparisons.

Show the answer

The search returns -1. The outer loop runs for start values from 0 up to n - m, which is 3 minus 4, or -1. Python's range(n - m + 1) is range(0), which is empty, so the loop body never runs and the function returns -1 at the end. No character is compared, so no index error can happen.

5. Write code that finds the text 1+1 inside 2+1+1=3 and prints the first start index. Then explain what happens to the same search without re.escape.

Show the answer

import re
 
match = re.search(re.escape("1+1"), "2+1+1=3")
print(match.start() if match else -1)

The output is 2, because 1+1 starts at index 2 of 2+1+1=3. Without re.escape, the + means "one or more of the character before it", so the regex 1+1 means one or more 1 characters followed by a 1. That needs two 1 characters in a row, and 2+1+1=3 has none, so re.search("1+1", "2+1+1=3") returns None and the program prints -1. The plain "2+1+1=3".find("1+1") returns 2, because find never reads the plus as a rule.

Summary

• A substring search tries each start position from 0 to n - m and compares the pattern with the text at that position.
• The inner loop stops at the first mismatch, and the outer loop moves to the next start.
• In the worst case, the naive search costs (n - m + 1) * m comparisons, which grows roughly as n * m.
• str.find gives the first index of a plain substring, and find(pattern, start) starts at any index.
• re.search searches with a regular expression. Wrap plain text with re.escape so its characters are not read as regex rules.
• re.finditer with a lookahead finds overlapping matches, and str.count does not.
• Keep the outer loop bound at n - m, because a looser bound reads past the end of the text and raises an error.