How to implement naive substring search?

AlgorithmsJunior~2 min read

Short answer

Naive substring search sequentially checks every position i in the text (0..n−m), comparing the pattern of length m to the text character by character. On a full match it returns index i (or accumulates every i); on a mismatch it shifts by 1. Time complexity: O(n·m) in the worst case, O(n) in the best case (with early mismatches), O(1) memory.

Detailed explanation

Algorithm idea

Iterate over every shift i from 0 to n−m.
For each i, compare the characters pattern[0..m−1] against text[i..i+m−1].
If all m characters match, an occurrence is found.
Otherwise, increment i by 1 and repeat.
Boundaries: if m = 0, return 0 (or every index, depending on the task); if m > n, there are no matches.

Pseudocode

function naiveSearch(text, pattern):
    n = length(text)
    m = length(pattern)
    if m == 0:
        return 0
    if m > n:
        return -1
    for i from 0 to n - m:
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        if j == m:
            return i
    return -1

Implementation

JavaScript

function naiveSearch(text, pattern, all = false) {
  const n = text.length;
  const m = pattern.length;
  if (m === 0) return all ? [...Array(n + 1).keys()] : 0;
  if (m > n) return all ? [] : -1;

  const results = [];
  for (let i = 0; i <= n - m; i++) {
    let j = 0;
    while (j < m && text[i + j] === pattern[j]) j++;
    if (j === m) {
      if (!all) return i;
      results.push(i);
    }
  }
  return all ? results : -1;
}

// Examples:
// naiveSearch("abracadabra", "abra") -> 0
// naiveSearch("abracadabra", "abra", true) -> [0, 7]
// naiveSearch("aaaaa", "aa", true) -> [0, 1, 2, 3]

Python

def naive_search(text: str, pattern: str, all: bool = False):
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1)) if all else 0
    if m > n:
        return [] if all else -1

    found = []
    for i in range(n - m + 1):
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        if j == m:
            if not all:
                return i
            found.append(i)
    return found if all else -1

# Usage examples:
# naive_search("abracadabra", "abra") -> 0
# naive_search("abracadabra", "abra", all=True) -> [0, 7]
# naive_search("aaaaa", "aa", all=True) -> [0, 1, 2, 3]

Example (step by step)

Let text = "ababa", pattern = "aba".

i = 0: compare "aba" with text[0..2] = "aba", all 3 characters match, an occurrence at 0.
i = 1: compare pattern[0] = 'a' with text[1] = 'b', a mismatch, shift.
i = 2: compare text[2..4] = "aba", a match, an occurrence at 2 (if collecting every occurrence).

Complexity

Time: worst case O(n·m) (for example, text = "aaaaa…a", pattern = "aaaab").
Best case: O(n) with early mismatches (for example, the pattern's first character rarely occurs).
Average: on random data, often close to O(n), but there is no theoretical guarantee.
Memory: O(1).

Edge cases and correctness

Empty pattern: by convention, return 0 (or every index 0..n, if searching for all).
A pattern longer than the text: there are no matches.
Overlapping occurrences: the naive algorithm correctly finds them if every position i is checked (see the "aaaaa" and "aa" example).
Correctness: the invariant is that by the time position i is checked, it is already proven that no position < i can be the start of a match (it was checked fully).

When to use it, and alternatives

Use it: short strings, a one-off search, simplicity matters more than speed, limited resources.
Do not use it: large texts or repeated searches, KMP (O(n+m)) is better, Boyer-Moore/Horspool (good practice on large alphabets), Rabin-Karp (searching for multiple patterns with hashes).

Typical interview questions

How do you handle an empty pattern and Unicode graphemes?
How do you find every occurrence, including overlapping ones?
Why is the worst-case complexity O(n·m), and which inputs reach it?
How does the naive approach differ from KMP/Boyer-Moore?

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.