Naive String Matching
Compare the pattern at every text position — simple, correct, and a baseline for faster methods.
The Pattern-Matching Problem
Given a text T of length n and a pattern P of length m (typically m ≪ n), report every index s where P occurs as a contiguous substring of T starting at position s (0-based or 1-based, depending on convention).
The naive idea: try every possible alignment s = 0, 1, …, n − m and check whether T[s..s+m−1] equals P.
How the Naive Algorithm Works
For each shift s from 0 to n − m:
- Compare P[0] with T[s], P[1] with T[s+1], … until all m characters match or a mismatch appears.
- If all match, record s as a valid occurrence.
No preprocessing — you only need the strings themselves.
Strengths and Weaknesses
Pros: Extremely easy to implement and reason about; uses O(1) extra space beyond the input.
Cons: Worst-case time is O((n − m + 1) · m), i.e. O(nm) when m is not treated as a constant. Adversarial inputs (e.g. T = "aaaa…a", P = "aa…ab") force many redundant comparisons.
Faster algorithms (Rabin–Karp, KMP, Boyer–Moore) reduce or eliminate this worst-case or average behavior.
Pseudocode
The double loop is the direct translation of “try every shift, compare character by character.”
1NAIVE-STRING-MATCHER(T, n, P, m)2 occurrences = []3 for s = 0 to n - m4 j = 05 while j < m and T[s + j] = P[j]6 j = j + 17 if j = m8 occurrences.append(s)9 return occurrences
Complexity
Time: O(nm) worst case; O(n) best case when the first character of P rarely matches T (many shifts fail immediately).
Space: O(1) auxiliary space if you count only pointers and counters.
Complexity Analysis
Time Complexity
O(nm) worst case
Space Complexity
O(1) auxiliary
Best case can be much better when early mismatches are common