Naive Substring Search

Description

Finding where a pattern first appears in a text is the core of every editor's Find, of grep and of log filtering. The simplest method tries every alignment, and for most real text it's fast. Knowing exactly when it isn't, and what to use then, matters more than the code. This skill covers the naive scan, the rolling-hash speed-up (Rabin-Karp), and the hashing pitfalls that turn fingerprints into false matches.

We'll go from simple to more technical:

1. The pattern: try every alignment, comparing in place.
2. A second flavor: a rolling hash, with every hash match verified.
3. Where substring search runs in production (Find, grep, log filters, signature scanning).
4. What breaks it: loop bounds, repetitive input, per-position copies, trusting hashes.

The approach

int strStr(String haystack, String needle) {
    int n = haystack.length(), m = needle.length();
    for (int i = 0; i + m <= n; i++) {                    // every start where the needle still fits
        int j = 0;
        while (j < m && haystack.charAt(i + j) == needle.charAt(j)) j++;
        if (j == m) return i;                             // all m characters matched
    }
    return -1;
}

def str_str(haystack: str, needle: str) -> int:
    n, m = len(haystack), len(needle)
    for i in range(n - m + 1):                       # every start where the needle still fits
        j = 0
        while j < m and haystack[i + j] == needle[j]:
            j += 1
        if j == m:
            return i                                 # all m characters matched
    return -1

The bound i + m <= n allows the last possible alignment, where the needle ends on the text's last character (in Python, range(n - m + 1)). i < n - m misses exactly that alignment ("abc" and "c" returns -1), and i < n reads past the end.

Each alignment compares characters until the first mismatch. On ordinary text that happens almost immediately, so the search is close to O(n). On repetitive text it doesn't: searching 200,000 'a's for 1,000 'a's followed by a 'b' compares about 1,000 characters at every one of 199,000 alignments - 199 million comparisons, O(n * m). Compare in place, too: haystack.substring(i, i + m).equals(needle) copies a new string at every position, while haystack.startsWith(needle, i) doesn't. In Python, too, haystack[i:i + m] == needle copies a slice and haystack.startswith(needle, i) doesn't.

A second flavor: a rolling hash (Rabin-Karp)

Instead of comparing characters at every alignment, compare a fingerprint of each window with the needle's - and update the window's fingerprint in O(1) as it slides:

int rabinKarp(String text, String needle) {
    int n = text.length(), m = needle.length();
    if (m > n) return -1;
    final long B = 256, P = 1_000_000_007L;
    long pow = 1, hn = 0, h = 0;
    for (int k = 0; k < m; k++) {
        if (k > 0) pow = pow * B % P;                     // B^(m-1) mod P
        hn = (hn * B + needle.charAt(k)) % P;
        h = (h * B + text.charAt(k)) % P;
    }
    for (int i = 0; ; i++) {
        if (h == hn && text.startsWith(needle, i)) return i;   // equal hashes can still differ: verify
        if (i + m == n) return -1;
        h = (h - text.charAt(i) * pow % P + P) % P;            // drop the leftmost character
        h = (h * B + text.charAt(i + m)) % P;                  // append the next one
    }
}

def rabin_karp(text: str, needle: str) -> int:
    n, m = len(text), len(needle)
    if m > n:
        return -1
    B, P = 256, 1_000_000_007
    pow_b = pow(B, m - 1, P)                         # B^(m-1) mod P
    hn = h = 0
    for k in range(m):
        hn = (hn * B + ord(needle[k])) % P
        h = (h * B + ord(text[k])) % P
    for i in range(n - m + 1):
        if h == hn and text.startswith(needle, i):
            return i                                 # equal hashes can still differ: verify
        if i + m < n:
            h = (h - ord(text[i]) * pow_b) % P       # drop the leftmost character (Python's % is never negative)
            h = (h * B + ord(text[i + m])) % P       # append the next one
    return -1

The expected cost is O(n + m): characters are compared only when the hashes agree, and with a large prime that's almost always a real match. The verification is not optional - different windows can share a hash. For very small alphabets an exact encoding avoids collisions entirely: with A, C, G, T as 2-bit codes, a 10-letter DNA window is a 20-bit int, updated with window = ((window << 2) | code) & ((1 << 20) - 1).

Where you'll see it

Java's String.indexOf is exactly this try-every-alignment scan; HotSpot runs it with SIMD instructions, which makes it fast but leaves the worst case O(n * m). C's glibc strstr uses the Two-Way algorithm, linear in the worst case, and GNU grep uses Boyer-Moore-style skipping. Rolling hashes power rsync, which finds matching blocks between file versions with a rolling checksum, and content-defined chunking in backup and deduplication tools.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why is the loop bound i + m <= n and not i < n - m?

2. What input makes naive search do the most work?

3. Why does Rabin-Karp compare characters when the hashes are equal?

Key takeaways

• Try every start with i + m <= n; compare in place, not with substring.
• Naive search is near O(n) on typical text but O(n * m) on repetitive text - and Java's indexOf is naive.
• Rabin-Karp slides a hash in O(1) per step and must verify hash matches.
• Tiny alphabets allow exact rolling encodings (2 bits per DNA letter).
• For guaranteed linear time, use KMP (or Two-Way).