String Matching (Substring Search)

Concept

Problem: Given a text “Haystack” (length N) and a pattern “Needle” (length M), find the starting index of the first occurrence of the Needle in the Haystack.
Haystack: "hello", Needle: "ll" -> Returns 2

This is the exact algorithm underlying indexOf() or includes() in modern programming languages.
While high-level languages handle this for you, interviewers (especially at FAANG) will occasionally ask you to implement the underlying search algorithm yourself to test your algorithmic depth.

Approach 1: The Naive Search ($O(N \times M)$)

The simplest approach. You slide the Needle along the Haystack one character at a time. If the first character matches, you start an inner loop to check the rest of the Needle. If it fails, you reset and move the Needle over by 1.

function naiveSearch(haystack: string, needle: string): number {
    if (needle === "") return 0;
    
    // We only need to slide until there isn't enough room left for the needle
    for (let i = 0; i <= haystack.length - needle.length; i++) {
        let j = 0;
        // Inner loop checking the needle
        while (j < needle.length && haystack[i + j] === needle[j]) {
            j++;
        }
        // If we matched the entire needle, we found it!
        if (j === needle.length) return i;
    }
    return -1;
}

Why it’s bad: Imagine Haystack: "AAAAAAAAAAAAAAAAAB" and Needle: "AAAAAB". The inner loop checks 5 ‘A’s, hits the ‘B’, fails, and resets. Then it checks 5 ‘A’s again, hits the ‘B’, fails, and resets. It does massive amounts of duplicated work.

Approach 2: Rabin-Karp (Rolling Hash)

This is a brilliant $O(N)$ average time algorithm.
Instead of comparing characters, it mathematically calculates a Hash Value for the Needle.
Then, it slides a window of size M across the Haystack, calculating the Hash Value for the window. If the window’s hash matches the Needle’s hash, we found the substring!

The Trick (The Rolling Hash):
Recalculating a string hash from scratch normally takes $O(M)$ time. If we do that for every window, we are back to $O(N \times M)$.
Rabin-Karp uses a “Rolling Hash”. When the window slides, it takes the previous hash, mathematically subtracts the character falling out of the window, and mathematically adds the character entering the window. This updates the hash in blazing-fast $O(1)$ time!

Approach 3: KMP Algorithm (Knuth-Morris-Pratt)

This is the absolute most optimal $O(N)$ worst-case algorithm. It is notoriously difficult to implement in an interview unless you have memorized it.
It works by pre-processing the Needle to build an “LPS Array” (Longest Proper Prefix which is also Suffix).
When a mismatch occurs during the search, instead of shifting the Needle over by exactly 1 and starting from scratch, KMP looks at the LPS array and mathematically deduces exactly how far it can safely “jump” the Needle forward, completely bypassing characters it already knows it matched.

Interview Questions

Q: If KMP is $O(N)$ and strictly faster than the Naive Search’s $O(N \times M)$, why do many standard libraries (like Python’s string.find) still use variations of the Naive approach (like Boyer-Moore) instead of KMP?
A: Because Big-O is just a theoretical upper bound.
While KMP guarantees $O(N)$ worst-case, it requires pre-processing the Needle to build an array, which requires $O(M)$ extra memory allocation and time upfront.
In the real world, English text is highly randomized. The worst-case scenario (AAAAAAAAB) almost never happens. A highly optimized Naive search (especially one like Boyer-Moore that searches backwards and jumps) practically runs in $O(N)$ time on real English text, uses $O(1)$ space, and avoids the heavy overhead of allocating an LPS array.

Q: How does Rabin-Karp handle Hash Collisions?
A: Just like a Hash Map, two completely different strings can mathematically generate the exact same Hash Value (e.g., hash("cat") === 123 and hash("dog") === 123).
Therefore, if Rabin-Karp detects that the windowHash === needleHash, it cannot blindly return true. It must trigger a manual character-by-character check ($O(M)$ time) to verify it is a true match and not a collision. If it is a collision, it ignores it and continues sliding the window.