DEV Community

DevCorner2
DevCorner2

Posted on

🔥 Blog 1: String Matching Algorithms in DSA (KMP, Rabin-Karp, Z-Algorithm)

String matching is one of the most fundamental problems in computer science, forming the backbone of text editors, search engines, compilers, and bioinformatics. In interviews, string matching problems are frequently asked to test your algorithmic depth and efficiency.

In this blog, we’ll cover the top three string matching algorithms you must know:

  • ✅ Naïve Approach (Baseline)
  • ✅ Knuth-Morris-Pratt (KMP) Algorithm
  • ✅ Rabin-Karp Algorithm
  • ✅ Z-Algorithm

1. Naïve String Matching (Baseline)

Idea: For each index in the text, check if the pattern matches starting there.

  • Time Complexity: O(n * m) (n = text length, m = pattern length). 
class NaiveSearch {
    public static void search(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();

        for (int i = 0; i <= n - m; i++) {
            int j;
            for (j = 0; j < m; j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) break;
            }
            if (j == m) {
                System.out.println("Pattern found at index " + i);
            }
        }
    }

    public static void main(String[] args) {
        search("ababcabcabababd", "ababd");
    }
}
Enter fullscreen mode Exit fullscreen mode

2. Knuth-Morris-Pratt (KMP) Algorithm

Key Idea: Avoid re-checking characters by precomputing the Longest Prefix Suffix (LPS) array.

  • Time Complexity: O(n + m)
  • Space Complexity: O(m) 
class KMP {
    public static void KMPSearch(String text, String pattern) {
        int n = text.length(), m = pattern.length();

        int[] lps = computeLPS(pattern);
        int i = 0, j = 0;

        while (i < n) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++; j++;
            }
            if (j == m) {
                System.out.println("Pattern found at index " + (i - j));
                j = lps[j - 1];
            } else if (i < n && text.charAt(i) != pattern.charAt(j)) {
                if (j != 0) j = lps[j - 1];
                else i++;
            }
        }
    }

    private static int[] computeLPS(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m];
        int len = 0, i = 1;

        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                lps[i++] = ++len;
            } else {
                if (len != 0) len = lps[len - 1];
                else lps[i++] = 0;
            }
        }
        return lps;
    }

    public static void main(String[] args) {
        KMPSearch("ababcabcabababd", "ababd");
    }
}
Enter fullscreen mode Exit fullscreen mode

3. Rabin-Karp Algorithm

Key Idea: Use rolling hash to quickly compare substrings with the pattern.

  • Time Complexity: O(n + m) on average, O(nm) worst case.
  • Great for multiple pattern matching. 
class RabinKarp {
    static final int d = 256; // number of characters
    static final int q = 101; // prime modulus

    public static void search(String text, String pattern) {
        int n = text.length(), m = pattern.length();
        int pHash = 0, tHash = 0, h = 1;

        for (int i = 0; i < m - 1; i++) h = (h * d) % q;

        for (int i = 0; i < m; i++) {
            pHash = (d * pHash + pattern.charAt(i)) % q;
            tHash = (d * tHash + text.charAt(i)) % q;
        }

        for (int i = 0; i <= n - m; i++) {
            if (pHash == tHash && text.substring(i, i + m).equals(pattern)) {
                System.out.println("Pattern found at index " + i);
            }
            if (i < n - m) {
                tHash = (d * (tHash - text.charAt(i) * h) + text.charAt(i + m)) % q;
                if (tHash < 0) tHash += q;
            }
        }
    }

    public static void main(String[] args) {
        search("ababcabcabababd", "ababd");
    }
}
Enter fullscreen mode Exit fullscreen mode

4. Z-Algorithm

Key Idea: Precompute Z-array, where Z[i] = length of longest prefix of the string that is also a substring starting at i.

  • Time Complexity: O(n + m)
  • Used in pattern search, palindrome problems, DNA sequencing. 
class ZAlgorithm {
    public static void search(String text, String pattern) {
        String concat = pattern + "$" + text;
        int n = concat.length();
        int[] Z = computeZ(concat);

        for (int i = 0; i < n; i++) {
            if (Z[i] == pattern.length()) {
                System.out.println("Pattern found at index " + (i - pattern.length() - 1));
            }
        }
    }

    private static int[] computeZ(String s) {
        int n = s.length();
        int[] Z = new int[n];
        int L = 0, R = 0;

        for (int i = 1; i < n; i++) {
            if (i <= R) Z[i] = Math.min(R - i + 1, Z[i - L]);
            while (i + Z[i] < n && s.charAt(Z[i]) == s.charAt(i + Z[i])) Z[i]++;
            if (i + Z[i] - 1 > R) {
                L = i; R = i + Z[i] - 1;
            }
        }
        return Z;
    }

    public static void main(String[] args) {
        search("ababcabcabababd", "ababd");
    }
}
Enter fullscreen mode Exit fullscreen mode

📌 When to Use What?

  • Naïve: Small inputs, easy debugging.
  • KMP: Best for single-pattern search, guaranteed O(n + m).
  • Rabin-Karp: Multiple pattern matching, plagiarism detection.
  • Z-Algorithm: Used in advanced string problems (substring search, palindromes, compression).

✅ Key Takeaway

String matching is a high-frequency interview topic. Mastering KMP, Rabin-Karp, and Z-Algorithm will help you ace questions on substring search, text analysis, and bioinformatics-style problems.

👉 Next in this series (Blog 2), we’ll move upwards in our list: Topological Sort & Kahn’s Algorithm (used in scheduling, dependency resolution, course schedule problems).

Top comments (0)