Naive Pattern Matching (Brute-Force Substring Search)

Naive matching tries every alignment: for each start index, compare pattern character by character until mismatch or success. Complexity O(n*m) but implementation is short and correct—a baseline before KMP.

Why this shows up in the real world

Small config files where n and m are tiny often use naive search for clarity. Teaching compilers start with brute substring search before optimizing.

Core idea (explained for students)

Triple loop structure: for i in range(len(text)-len(pat)+1): j=0 while j<m and text[i+j]==pat[j]: j+=1 then if j==m: yield i.

Try this in Python

def find_all(text: str, pat: str) -> list[int]:
    n, m = len(text), len(pat)
    if m == 0 or m > n:
        return []
    out = []
    for i in range(n - m + 1):
        if text[i : i + m] == pat:
            out.append(i)
    return out


print(find_all("abababa", "aba"))

Common mistakes

• Loop upper bound off-by-one when len(pat) > len(text).
• Returning match list vs first match—read problem statement.

Key takeaways

• Always implement naive once—it validates test cases for faster algorithms.
• Early break on first mismatch keeps inner loop tight.