KMP Pattern Matching, Rabin-Karp & Z Algorithm

Advanced String Pattern Matching

Naive matching takes $O(N \times M)$ time. **KMP** uses Longest Prefix Suffix (LPS) array for $O(N + M)$ time. **Rabin-Karp** uses Rolling Hash. **Z Algorithm** builds Z-array.

Production Code Example:

public class KmpSearch {
    public int strStr(String haystack, String needle) {
        if (needle.isEmpty()) return 0;
        int[] lps = buildLPS(needle);
        int i = 0, j = 0;
        while (i < haystack.length()) {
            if (haystack.charAt(i) == needle.charAt(j)) { i++; j++; }
            if (j == needle.length()) return i - j;
            else if (i < haystack.length() && haystack.charAt(i) != needle.charAt(j)) {
                if (j != 0) j = lps[j - 1]; else i++;
            }
        }
        return -1;
    }
    private int[] buildLPS(String pat) {
        int[] lps = new int[pat.length()];
        int len = 0, i = 1;
        while (i < pat.length()) {
            if (pat.charAt(i) == pat.charAt(len)) lps[i++] = ++len;
            else if (len != 0) len = lps[len - 1]; else lps[i++] = 0;
        }
        return lps;
    }
}

Key Complexity & Algorithmic Takeaways:

When implementing KMP Pattern Matching, Rabin-Karp & Z Algorithm in coding interviews and production applications, keep these core guidelines in mind:

• Time Complexity Analysis: Always evaluate best-case, average-case, and worst-case time complexities ($O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$).
• Space Complexity & Memory Bounds: Account for auxiliary memory usage, call stack frame recursion overhead, and heap allocations.
• Edge Cases & Validation: Test empty inputs, null pointers, single-element collections, duplicate values, and integer overflow bounds.
• Optimal vs Naive Solutions: Start with a clear brute-force solution, then optimize using techniques like Hashing, Two Pointers, Windowing, or Dynamic Programming.

Summary Takeaway:

Mastering KMP Pattern Matching, Rabin-Karp & Z Algorithm provides the foundational problem-solving skills needed to pass technical coding interviews at top tech companies and write ultra-performant software systems.