Brute-force Algorithm (String Matching)

Definition

Brute-force Algorithm (String Matching)

Given a text $T=t_1\dots t_n$ and a pattern $P=p_1\dots p_m$, the brute-force algorithm for the string matching problem tests every possible starting position. At each position, it compares pattern characters with text characters from left to right until a mismatch occurs or the whole pattern matches. It returns

$$\{i\in \{1,\dots ,n-m+1\}:\forall j\in \{1,\dots ,m\},t_{i+j-1}=p_j\}.$$

After each test, the starting position advances by one, so overlapping occurrences are retained. If $m>n$, there are no occurrences. The empty string occurs at all $n+1$ boundaries of the text.

Pseudocode

Indices are one-based. An integer range is empty when its upper bound is smaller than its lower bound.

string_matching_bruteforce(T, P):
    n := |T|
    m := |P|
    occurrences := []
    for i := 1 to n - m + 1:
        j := 1
        while j <= m and T[i + j - 1] == P[j]:
            j := j + 1
        if j == m + 1:
            append i to occurrences
    return occurrences

The and condition short-circuits: no character is accessed once j > m. Thus an empty pattern is accepted at every boundary without a character comparison.

Correctness

Exact Occurrence Positions

The algorithm returns every occurrence of $P$ in $T$, and no other position.

Proof

At the start of each inner-loop iteration, the first $j-1$ pattern characters match the text at the current alignment:

$$\forall k\in \{1,\dots ,j-1\},t_{i+k-1}=p_k.$$

This holds initially because no characters have been compared. Each successful comparison extends the matching prefix by one character.

No false positives: a position is appended only when $j=m+1$, so all $m$ characters match.

No missed occurrences: the outer loop visits every valid starting position. At an actual occurrence, every comparison succeeds, so the position is appended. A mismatch rejects only the current alignment.

For $m>n$, the outer loop is empty. For $m=0$, the matching condition is vacuous, so all $n+1$ boundaries are returned.

Complexity

For $1\le m\le n$, there are $n-m+1$ alignments and at most $m$ character comparisons per alignment. The worst-case time complexity is

$$\underset{\text{alignments}}{\underbrace{n-m+1}}\cdot \underset{\text{work per alignment}}{\underbrace{\Theta (m)}}=\Theta ((n-m+1)m),$$

which is $O(nm)$. The bound is attained by $T=a^n$ and $P=a^m$: every alignment requires all $m$ comparisons. Unlike the exponential enumeration for longest common subsequence, this algorithm enumerates only contiguous starting positions.

If $m>n$, the running time is $\Theta (1)$. If $m=0$, returning all boundaries takes $\Theta (n+1)$ time.

Auxiliary space is $O(1)$, excluding the output list, which stores $k$ occurrence positions in $O(k+1)$ space.

Examples

Overlapping occurrences

Let $T=\text{ababa}$ and $P=\text{aba}$.

• At $i=1$, all three characters match: append $1$.
• At $i=2$, the first comparison fails because $\text{b}\ne \text{a}$.
• At $i=3$, all three characters match: append $3$.

The result is $[1,3]$. Advancing by one rather than by the pattern length preserves the overlapping occurrence at position $3$.