Naive String Search

#How does it work?

String matching means finding every position where a pattern occurs in a text. The simplest method places the pattern at every possible starting position of the text and compares letter by letter.

At each shift the comparison starts at the beginning of the pattern and stops at the first mismatch; the pattern moves one step right and everything starts over. If every letter matches, a match is found.

It is fast on most real text, because mismatches usually show up within the first few letters. But on repetitive text such as AAAA…AB the same letters are compared again and again and the cost rises to O(n · m).

#Try it yourself

#Step by step

1. 01Align the pattern with the first position of the text.
2. 02Compare letters from the start; stop at the first mismatch.
3. 03If every letter matched, record the match.
4. 04Move the pattern one step right and repeat up to the last position.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

def search(text: str, pattern: str) -> list:
    """Every 0-based position where pattern starts in text."""
    n, m = len(text), len(pattern)
    found = []
    for s in range(n - m + 1):  # every shift of the pattern
        j = 0
        while j < m and text[s + j] == pattern[j]:
            j += 1
        if j == m:
            found.append(s)
    return found


print(" ".join(map(str, search("AABAACAADAABAABA", "AABA"))))

#Complexity

n is the text length and m the pattern length. The pattern is tried at n − m + 1 shifts with at most m comparisons each. Since it needs no preprocessing, it remains a good choice for short patterns and one-off searches.

#When to use it?

Short patterns and short texts, one-off searches and places where simplicity matters. Many standard libraries' indexOf / find use an optimised form of this method for short inputs.

#Practice

Log in to answer questions and save your progress.

#Up next

Lessons that build on this one:

• KMP Algorithm
• Rabin-Karp Algorithm