Lesson 12 of 16

Find a Pattern in Text

Finding a word in a document means finding a contiguous occurrence. Unlike LCS in lesson 8, characters cannot be skipped.

The direct method

Try each possible starting position and compare the pattern’s characters in order.

def find_pattern(text, pattern):
    if not pattern:
        return 0
    for start in range(len(text) - len(pattern) + 1):
        matched = True
        for offset in range(len(pattern)):
            if text[start + offset] != pattern[offset]:
                matched = False
                break
        if matched:
            return start
    return -1

print(find_pattern("ababc", "abc"))

The result is 2, using zero-based indexes. We define an empty pattern to match at position 0. A pattern longer than the text has no candidate position, so the result is -1.

For text length n and pattern length m, each start may require m comparisons, giving O(nm) worst-case time. Searching for aaab in aaaaab illustrates repeated comparisons of similar text.

KMP reuses failed comparisons

KMP precomputes how prefixes and suffixes of the pattern overlap. For example, abab begins and ends with ab. If matching fails after abab, that already matched ending can serve as the beginning of the next candidate.

This overlap information lets the text position keep moving forward. Preparing the pattern takes O(m) and searching takes O(n), for O(n+m) overall. The key is constructing the table of fallback positions correctly.

Other methods have assumptions too

• Rabin-Karp: Compare substring hashes, then verify actual characters because hashes can collide.
• Boyer-Moore: Compare from the pattern’s end and skip using mismatch information. Time guarantees depend on the implementation and rules used.
• For ordinary application search, first consider the language’s built-in search functions.

Check your understanding

How many occurrences of aa are in aaaa? Can you always move forward by the pattern length after a match?