String Pattern Matching

1. Introduction: The Search Query

Imagine hitting Ctrl+F in a 1,000,000-word document to search for a 10-letter word. The brute force approach is to check index 0. Do the next 10 letters match? If not, check index 1. Do the next 10 letters match? This takes $O(N \times M)$ time. If $N = 10^6$ and $M = 10$, that's $10^7$ operations. Acceptable. But what if you are searching a DNA sequence ($N = 10^9$) for a specific massive gene sequence ($M = 10^5$)? The brute force takes $10^{14}$ operations, which will crash your server.

We need algorithms that can search for a pattern in $O(N + M)$ time. The two undisputed kings of this domain are Rabin-Karp (which uses Hashing) and KMP (which uses a mathematical Prefix Table).

2. Core Concept 1: Rabin-Karp (Rolling Hash)

Instead of comparing characters one by one, what if we convert the pattern into an integer hash code? (e.g., "abc" -> 123). Then, we convert a sliding window of the text into a hash code. If hash(window) == hash(pattern), we have a match!

The Trick: Generating a hash from scratch takes $O(M)$. We can't do that for every window! We must use a Rolling Hash. When the window slides right, we mathematically subtract the value of the character falling out on the left, multiply by the base to shift the numbers, and add the new character on the right. This takes $O(1)$ time!

public class RabinKarp {
    // We use a prime number as the base, and modulo to prevent integer overflow
    private static final int BASE = 256;
    private static final int MOD = 1000000007;

    public int search(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        if (m > n || m == 0) return -1;

        long patternHash = 0;
        long windowHash = 0;
        long h = 1; // Used for removing the leftmost digit

        // 1. Calculate 'h' = Math.pow(BASE, m-1) % MOD
        for (int i = 0; i < m - 1; i++) {
            h = (h * BASE) % MOD;
        }

        // 2. Calculate the initial hash for the pattern and the first window
        for (int i = 0; i < m; i++) {
            patternHash = (BASE * patternHash + pattern.charAt(i)) % MOD;
            windowHash = (BASE * windowHash + text.charAt(i)) % MOD;
        }

        // 3. Slide the window over the text
        for (int i = 0; i <= n - m; i++) {
            // If hashes match, verify character-by-character (to handle hash collisions)
            if (patternHash == windowHash) {
                if (text.substring(i, i + m).equals(pattern)) {
                    return i; // Match found!
                }
            }

            // Rolling Hash: Remove leftmost char, shift base, add rightmost char
            if (i < n - m) {
                windowHash = (BASE * (windowHash - text.charAt(i) * h) + text.charAt(i + m)) % MOD;
                
                // If windowHash became negative during subtraction, make it positive
                if (windowHash < 0) {
                    windowHash += MOD;
                }
            }
        }
        return -1;
    }
}

Time Complexity: Average $O(N+M)$. Worst case $O(N \times M)$ if the hash function causes collisions everywhere.

3. Core Concept 2: KMP (Knuth-Morris-Pratt)

KMP guarantees strictly $O(N+M)$ time. It does this by never moving the text pointer backwards. If we are matching "ABCDABD", and we successfully match "ABCDAB", but fail on the last "D", we don't start over from the beginning! We noticed that "AB" appears at the start AND the end of what we just matched. We can just slide the pattern forward and instantly resume checking from "AB...".

The LPS Array: KMP requires building a "Longest Prefix Suffix" array for the pattern. lps[i] stores the length of the longest proper prefix that is also a suffix in pattern[0..i].

public class KMPAlgorithm {
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        if (m == 0) return 0;
        
        // 1. Build the LPS Array
        int[] lps = buildLPS(needle);
        
        // 2. Search
        int i = 0; // index for haystack
        int j = 0; // index for needle
        
        while (i < n) {
            if (needle.charAt(j) == haystack.charAt(i)) {
                i++;
                j++;
            }
            
            if (j == m) {
                return i - j; // Match found! Return start index
                // j = lps[j - 1]; // Use this if searching for ALL occurrences
            } 
            else if (i < n && needle.charAt(j) != haystack.charAt(i)) {
                if (j != 0) {
                    // Mismatch! Use LPS to skip redundant checks
                    j = lps[j - 1]; 
                } else {
                    i++;
                }
            }
        }
        return -1;
    }
    
    private int[] buildLPS(String pattern) {
        int[] lps = new int[pattern.length()];
        int length = 0; // length of previous longest prefix suffix
        int i = 1;
        
        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1]; // Fallback trick
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }
}

4. Advanced Concept: The Z-Algorithm

The Z-Algorithm is arguably easier to understand than KMP but achieves the exact same $O(N+M)$ time complexity. Instead of building a complex prefix-suffix table, it leverages a single concatenated string!

The Trick: You concatenate the pattern and the text with a rare delimiter (e.g., pattern + "$" + text). You then generate a Z-Array where Z[i] is the length of the longest substring starting at i which is also a prefix of the entire concatenated string. If Z[i] == pattern.length(), you found a match!

(Note: The Z-Array generation uses complex boundary boxes [L, R] to copy previous Z-values to avoid redundant comparisons. It is rarely expected in interviews).

5. Common Mistakes Beginners Make

1. Forgetting Negative Modulo in Rabin-Karp

   • The Mistake: windowHash = (BASE * (windowHash - removedChar * h) + newChar) % MOD; without a negative check.
   • Why it's wrong: In Java, % is a remainder operator, not a true mathematical modulo. If (windowHash - removedChar * h) is negative, the result of the modulo will be negative! A negative hash will never match your positive patternHash.
   • The Fix: if (windowHash < 0) windowHash += MOD;.

2. Using KMP for simple problems

   • The Mistake: Spending 20 minutes trying to remember the LPS array logic for strStr (Find the Index of the First Occurrence in a String).
   • Why it's wrong: Most interviewers for LeetCode 28 just want to see a clean $O(N \times M)$ nested loop implementation with good boundary checks. Do not write KMP unless explicitly asked to optimize to $O(N+M)$.

3. Using Rabin-Karp Hash for Substring Verification

   • The Mistake: Returning true the moment patternHash == windowHash.
   • Why it's wrong: Hash Collisions! Two completely different strings can mathematically evaluate to the exact same hash code. When the hashes match, you MUST manually verify the characters using .equals() or a loop to confirm it is a true match.

6. Interview Q&A

Q1: Why is Rabin-Karp preferred in Plagiarism Detection? Answer: KMP only searches for ONE pattern. Rabin-Karp can search for MULTIPLE patterns simultaneously! If you have 100 sentences you want to check for plagiarism in a document, you hash all 100 sentences and store them in a HashSet. As your sliding window rolls across the document, you just check if the windowHash exists in the HashSet. It's $O(N)$ for infinite patterns!

Q2: What is the Tries (Prefix Tree) relationship to Pattern Matching? Answer: The Aho-Corasick algorithm merges Tries with KMP-style failure links. It is the ultimate algorithm for multi-pattern searching (used in grep and virus scanners), but is far beyond the scope of a standard FAANG interview.

7. Practice Problems

1. Find the Index of the First Occurrence in a String (LeetCode 28)
   • Goal: Implement Rabin-Karp and handle the negative modulo logic.
2. Repeated Substring Pattern (LeetCode 459)
   • Hint: Can be solved beautifully using the KMP LPS array. If n % (n - lps[n-1]) == 0, it's repeating!

8. Summary

• Rabin-Karp: Sliding window hash. Average $O(N+M)$. Best for multi-pattern matching. Watch out for negative modulo and collisions.
• KMP: Mathematical prefix-suffix table (LPS). Guaranteed $O(N+M)$. Never moves the text pointer backwards.
• The Reality: Unless specifically targeting a complex string problem, Java's built-in String.indexOf() uses highly optimized SIMD instructions at the CPU level and will often beat manual KMP implementations in real-world benchmarks.

Advanced Code Implementations

// Example: KMP Algorithm for Pattern Matching
public class KMP {
    public int strStr(String haystack, String needle) {
        if (needle.isEmpty()) return 0;
        int[] lps = computeLPS(needle);
        int i = 0, j = 0;
        while (i < haystack.length()) {
            if (needle.charAt(j) == haystack.charAt(i)) {
                i++; j++;
            }
            if (j == needle.length()) {
                return i - j;
            } else if (i < haystack.length() && needle.charAt(j) != haystack.charAt(i)) {
                if (j != 0) j = lps[j - 1];
                else i++;
            }
        }
        return -1;
    }
    
    private int[] computeLPS(String pat) {
        int[] lps = new int[pat.length()];
        int len = 0, i = 1;
        while (i < pat.length()) {
            if (pat.charAt(i) == pat.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) len = lps[len - 1];
                else { lps[i] = len; i++; }
            }
        }
        return lps;
    }
}

// Example: Rabin-Karp String Matching
public class RabinKarp {
    public int search(String text, String pattern) {
        int d = 256, q = 101;
        int M = pattern.length(), N = text.length();
        int i, j, p = 0, t = 0, h = 1;
        
        for (i = 0; i < M - 1; i++)
            h = (h * d) % q;
        for (i = 0; i < M; i++) {
            p = (d * p + pattern.charAt(i)) % q;
            t = (d * t + text.charAt(i)) % q;
        }
        for (i = 0; i <= N - M; i++) {
            if (p == t) {
                for (j = 0; j < M; j++) {
                    if (text.charAt(i + j) != pattern.charAt(j)) break;
                }
                if (j == M) return i;
            }
            if (i < N - M) {
                t = (d * (t - text.charAt(i) * h) + text.charAt(i + M)) % q;
                if (t < 0) t = (t + q);
            }
        }
        return -1;
    }
}

Expanded Interview Q&A

Q1: Why is KMP faster than naive string matching?

Answer: Naive matching backtracks the text pointer. KMP uses the Longest Prefix Suffix (LPS) array to skip redundant comparisons, strictly moving forward in the text.

Q2: What is the time complexity of building the LPS array?

Answer: O(M), where M is the length of the pattern.

Q3: What is a hash collision in Rabin-Karp?

Answer: It happens when two different strings produce the same hash value. This is why Rabin-Karp requires a character-by-character check when hashes match.

Q4: When would you use a Trie instead of KMP?

Answer: When you need to search for multiple different patterns simultaneously within a text, rather than just one.

Q5: How does a rolling hash work in Rabin-Karp?

Answer: It removes the contribution of the first character of the old window and adds the contribution of the new character in O(1) time.