Substring Search Algorithms

Find where a pattern appears inside a larger text. It's the engine behind Ctrl+F, grep, and every search bar you've ever used.

The simplest approach is brute force: try every starting position in the text, check if the pattern matches character by character. It's called the naive approach because it works, but it doesn't skip any work.

Naive substring search

For each position in the text, compare the pattern character by character. If all characters match, record the position.

function naiveSubstringSearch(text, pattern) {
    const occurrences = [];

    for (let i = 0; i <= text.length - pattern.length; i++) {
        let match = true;

        for (let j = 0; j < pattern.length; j++) {
            if (text[i + j] !== pattern[j]) {
                match = false;
                break;
            }
        }

        if (match) {
            occurrences.push(i);
        }
    }

    return occurrences;
}

Complexity

• Time: O(n * m) worst case, where n is the text length and m is the pattern length. Think of searching for "aaaaab" in "aaaaaaaaaa" — you almost match at every position before failing.
• Space: O(k) where k is the number of matches.

The trade-off

The naive approach is simple and works great for short patterns or one-off searches. But if you're searching the same text repeatedly, or the pattern is long, you want something smarter.

KMP (Knuth-Morris-Pratt) preprocesses the pattern to skip redundant comparisons — O(n + m) time. Boyer-Moore skips even more by matching from the end of the pattern. Rabin-Karp uses hashing for average O(n) performance.

For most JavaScript applications, String.prototype.indexOf() or includes() already uses an optimized algorithm internally. Know the naive approach to understand the problem. Use built-ins in production.