Find Every String Match

Practice Exercise Intermediate Medium String String Matching

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement find_occurrences(text, pattern). Return every start index where pattern occurs, including overlaps. An empty pattern matches every boundary from 0 through len(text). Do not use str.find or regex.

Starter code

def find_occurrences(text, pattern):
    pass

Test cases

overlap

{
  "args": [
    "aaaa",
    "aa"
  ]
}

Expected: [0,1,2]

missing

{
  "args": [
    "python",
    "java"
  ]
}

Expected: []

Wizard outline

Step 1: Define the empty-pattern boundary
Return every boundary position when the pattern is empty. The scan range and later offset loop both depend on this boundary.
Step 2: Scan complete text windows
Compare every pattern character at each non-overlapping candidate start. A candidate start is valid only when its full window equals the pattern.
Step 3: Preserve overlapping matches
Advance candidate starts one position at a time. Each start index is an independent candidate even when windows overlap.

Footguns and prerequisites

Advancing by pattern length skips overlaps.
The empty pattern has len(text)+1 valid boundaries.
strings

Reviewed references

Python More on Lists

Recommended approach and implementation

Try each legal start and compare pattern characters until mismatch or completion.

Why it works: Every possible match begins at one enumerated legal alignment. The inner comparison accepts exactly when all pattern positions agree, so all and only matches are returned, including overlaps.

def find_occurrences(text, pattern):
    matches = []
    for start in range(len(text) - len(pattern) + 1):
        matched = True
        for offset, character in enumerate(pattern):
            if text[start + offset] != character:
                matched = False
                break
        if matched:
            matches.append(start)
    return matches