Introduction

Searching for multiple words inside a body of text is one of the most common tasks in computer science. Applications range from spam filtering and plagiarism detection to DNA sequence matching and log analysis. Choosing the right algorithm can mean the difference between milliseconds and minutes on large inputs.

This article walks through four approaches, from brute-force to the Aho-Corasick automaton, with Python examples you can run immediately.

Naive (Brute-Force) Search

The most straightforward strategy is to iterate over every position in the text and, for each position, check whether any of the target words starts there. For n characters of text and a word list whose combined length is m, the worst-case time complexity is O(n * m).

1def naive_multi_search(text, words):
2    """Return a dict mapping each word to the list of start indices where it appears."""
3    results = {w: [] for w in words}
4    for word in words:
5        wlen = len(word)
6        for i in range(len(text) - wlen + 1):
7            if text[i:i + wlen] == word:
8                results[word].append(i)
9    return results
10
11text = "the cat sat on the mat with another cat"
12words = ["cat", "mat", "the"]
13print(naive_multi_search(text, words))
14# {'cat': [4, 35], 'mat': [19], 'the': [0, 15]}

This works fine for short texts and small word lists, but performance degrades quickly because every word is checked independently against every position.

KMP (Knuth-Morris-Pratt)

KMP improves on the naive approach for a single pattern by precomputing a failure table. The table tells the algorithm how far to skip after a mismatch instead of rewinding. For one pattern of length m in text of length n, KMP runs in O(n + m) time.

For multiple patterns you run KMP once per pattern, giving O(n * k + M) where k is the pattern count and M is their total length. KMP is a good choice when your word list is small (roughly under ten words).

Trie-Based Filtering

A trie (prefix tree) stores all search words in a tree where each edge represents one character. To check whether any word starts at position i, walk the trie from the root while consuming characters. If you reach a node marked as a word ending, you have a match.

Building the trie costs O(M) time and space. Each text position takes at most O(L) to check, where L is the longest pattern length. The overall complexity is O(n * L + M), which beats naive search when patterns share common prefixes. However, a plain trie still restarts from position i + 1 after a mismatch. To eliminate that redundancy you need Aho-Corasick.

Aho-Corasick Algorithm

Aho-Corasick extends the trie with failure links, much like KMP extends naive single-pattern search. Failure links connect each node to the longest proper suffix of the current path that is also a prefix of some pattern. This lets the automaton continue matching without ever backing up in the text, giving a total time complexity of O(n + M + z) where z is the number of matches reported.

The ahocorasick PyPI package (pyahocorasick) provides an efficient C-backed implementation.

1import ahocorasick
2
3def aho_corasick_search(text, words):
4    """Return a dict mapping each word to the list of end indices where it appears."""
5    automaton = ahocorasick.Automaton()
6    for idx, word in enumerate(words):
7        automaton.add_word(word, (idx, word))
8    automaton.make_automaton()
9
10    results = {w: [] for w in words}
11    for end_index, (idx, word) in automaton.iter(text):
12        start_index = end_index - len(word) + 1
13        results[word].append(start_index)
14    return results
15
16text = "the cat sat on the mat with another cat"
17words = ["cat", "mat", "the"]
18print(aho_corasick_search(text, words))
19# {'cat': [4, 35], 'mat': [19], 'the': [0, 15]}

Aho-Corasick is the go-to algorithm when you have hundreds or thousands of patterns and a large text. It processes the text in a single linear pass regardless of how many patterns exist.

Choosing the Right Algorithm

Common Pitfalls

• Ignoring case sensitivity. Forgetting to normalize both the text and the patterns to the same case leads to missed matches. Always decide on a casing strategy before building your search structure.
• Rebuilding the automaton per query. The Aho-Corasick automaton is expensive to construct. If your word list is static, build it once and reuse it across many texts.
• Overlapping match confusion. Some algorithms report overlapping matches by default while others do not. Verify whether your use case needs overlapping results and configure accordingly.
• Unicode and multi-byte characters. Algorithms that index by byte position will produce wrong offsets for UTF-8 text containing multi-byte characters. Work with decoded strings, not raw bytes.
• Memory overhead of large tries. A trie for millions of long patterns can consume significant RAM. Consider compressed trie variants (DAFSA or double-array trie) when memory is a constraint.

Summary

• The naive approach checks every pattern at every position and is only suitable for small inputs.
• KMP adds a failure table to avoid redundant comparisons for a single pattern and works well when the word list is short.
• A trie stores all patterns in a shared prefix tree but still restarts after each mismatch.
• Aho-Corasick augments the trie with failure links so the entire text is scanned in one pass, making it the best choice for large-scale multi-word search.
• Always normalize text and patterns for case and encoding before searching.