Offensive Security Researcher & Quantum Cryptography Analyst

Naive String-Matching Algorithm: Detailed Explanation and Code Implementation

Abdul Wahab Junaid
Naive String-Matching Algorithm: Detailed Explanation and Implementation

I want to start by explaining what the naive string-matching algorithm actually is. When I need to find every place a small string (the “pattern”) appears inside a larger string (the “text”), the naive approach is the first idea that comes to my mind: I slide the pattern over the text one position at a time and check, character by character, whether it matches. I call this algorithm “naive” not because it is wrong, but because it does not use any clever preprocessing or auxiliary data structures the way algorithms like KMP, Boyer-Moore, or Rabin-Karp do. Even though it is simple, I still consider it important because it builds the intuition I need before I can appreciate why the smarter algorithms were invented.

History and Background

I trace the naive string-matching approach back to the very earliest days of computer science, long before formalized pattern-matching algorithms existed. Unlike KMP (Knuth-Morris-Pratt, 1977) or Boyer-Moore (1977), the naive method has no single inventor and no publication date I can point to — it is simply the brute-force method that any programmer would independently arrive at when asked to search for a substring. I mention it here mainly as the historical baseline against which the more sophisticated algorithms of the 1970s were measured and against which their performance improvements were proven.

Problem Statement

I define the problem as follows: given a text string T of length n and a pattern string P of length m (where m ≤ n), I want to find all starting indices s in T such that T[s..s+m-1] = P. In other words, I am looking for every occurrence of P as a substring of T.

Core Concepts

Before I explain the algorithm, I want to define a few terms I will keep using:

How It Works

I approach the problem by trying every possible alignment of the pattern against the text, from left to right:

  1. I place the pattern so its first character aligns with the text’s first character.
  2. I compare characters of the pattern and the text one by one, from left to right, within the current window.
  3. If all m characters match, I record the current index s as a valid shift (an occurrence).
  4. If I find a mismatch at any position, I stop comparing at this alignment.
  5. I shift the pattern one position to the right and repeat steps 2–4.
  6. I continue until the window slides past the end of the text (i.e., until s + m > n).

Working Principle

I think of the internal logic as two nested loops. The outer loop controls the alignment s, moving from 0 to n - m. The inner loop controls the character comparison j, moving from 0 to m - 1, comparing T[s + j] with P[j]. I do not skip any alignment and I do not reuse any information from a previous failed comparison — every alignment is checked completely independently. That lack of memory is precisely what makes the algorithm “naive,” and it is also what makes it easy for me to reason about and implement correctly.

Mathematical Foundation

I can express the matching condition formally. A shift s (with $0 \le s \le n – m$) is valid if and only if:

$$ T[s+j] = P[j] \quad \text{for all } j \in {0, 1, \dots, m-1} $$

The total number of alignments I must check is:

$$ n – m + 1 $$

For each alignment, I perform at most m character comparisons, so in the worst case the total number of character comparisons I perform is bounded by:

$$ (n – m + 1) \times m $$

which, when m is a constant fraction of n, simplifies to a bound of $O(nm)$.

Diagrams

flowchart TD
    A["Start"] --> B{"Is another position available?"}

    B -- Yes --> C["Initialize pattern index"]

    C --> D{"Pattern completely checked?"}

    D -- No --> E{"Characters match?"}
    D -- Yes --> F["Record the match"]

    E -- Yes --> G["Move to the next character"]
    G --> D

    E -- No --> H["Move to the next text position"]
    F --> H

    H --> B

    B -- No --> I["Report all matches and stop"]

Pseudocode

NAIVE-STRING-MATCH(T, P)
    n = length(T)
    m = length(P)
    for s = 0 to n - m
        j = 0
        while j

Step-by-Step Example

I will walk through a concrete example. Let me set:

I check each shift s from 0 to 5:

So the algorithm reports matches at shifts 0 and 5.

Time Complexity

I analyze the running time in three cases:

Space Complexity

I only need a constant amount of extra memory beyond the input strings themselves — variables for the indices s and j, and optionally a list to store the resulting match positions. So I consider the auxiliary space complexity to be $O(1)$, or $O(k)$ if I count the space needed to store k reported matches.

Correctness Analysis

I can argue correctness by exhaustion: the algorithm explicitly tries every possible alignment s from 0 to n - m, and for each one it checks every character position j from 0 to m - 1. Since I never skip an alignment and I never terminate a valid comparison early, I am guaranteed to detect every position where T[s..s+m-1] exactly equals P. There is no heuristic or shortcut that could cause me to miss a valid match or falsely report an invalid one, so the algorithm is trivially correct by direct verification of the matching condition.

Advantages

Disadvantages

Applications

I find the naive algorithm useful in:

Implementation in C

#include stdio.h>
#include string.h>

/* I implement the naive string matching algorithm.
   It prints every starting index where P occurs in T. */
void naiveStringMatch(const char *T, const char *P) {
    int n = strlen(T);
    int m = strlen(P);
    int found = 0;

    /* I try every possible alignment s */
    for (int s = 0; s  n - m; s++) {
        int j = 0;

        /* I compare pattern characters against the current window */
        while (j  m && T[s + j] == P[j]) {
            j++;
        }

        /* If I matched all m characters, I report this shift */
        if (j == m) {
            printf("Pattern found at index %d\n", s);
            found = 1;
        }
    }

    if (!found) {
        printf("Pattern not found in text.\n");
    }
}

int main(void) {
    const char *text = "ABABCABAB";
    const char *pattern = "ABAB";

    printf("Text: %s\n", text);
    printf("Pattern: %s\n", pattern);

    naiveStringMatch(text, pattern);

    return 0;
}

I keep the implementation deliberately minimal: I use strlen to compute lengths, then two loops exactly as described in the pseudocode. I chose to print each match as I find it rather than storing them, but I could easily change this to store indices in an array if I needed to process matches programmatically instead of printing them.

Sample Input and Output

Input:

Text: ABABCABAB
Pattern: ABAB

Output:

Text: ABABCABAB
Pattern: ABAB
Pattern found at index 0
Pattern found at index 5

Optimization Techniques

Even though the naive algorithm is meant to be simple, I can still apply a few small optimizations without changing its fundamental character:

Common Mistakes

I have seen (and made) these mistakes when implementing this algorithm:

Further Reading

Exit mobile version