Suggest an edit

Improve this article

Refine the answer for “How to implement naive substring search?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## 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?

Markdown · drag & drop images · ⌘B / ⌘I shortcuts701 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.