Java Rabin-Karp Algorithm Tutorial 🎯

Welcome to our deep dive into the Rabin-Karp algorithm, a string searching algorithm that helps us find patterns within a larger text efficiently. This tutorial is perfect for beginners and intermediates who want to expand their programming skills. Let's get started! 🎉

What is the Rabin-Karp Algorithm? 📝

The Rabin-Karp algorithm is a string search algorithm that compares a pattern with a text to see if the pattern exists in the text. It's particularly useful when we have a large text and need to find a specific pattern quickly.

Why Use the Rabin-Karp Algorithm? 💡

Efficient: The Rabin-Karp algorithm reduces the time complexity for pattern search in a text from O(n^2) to O(n), making it suitable for large texts.
Versatile: It can handle patterns with repetitions and rotations, making it a more powerful tool compared to linear search and KMP algorithms.

Prerequisites 📝

Before diving into the Rabin-Karp algorithm, you should have a good understanding of the following concepts:

Java Basics
Data Structures (Arrays, Strings)
Modulo Operator (%)
BigInteger

Implementing the Rabin-Karp Algorithm 💡

Here's a step-by-step guide on how to implement the Rabin-Karp algorithm:

Define the pattern and text.
Calculate the hash values for the pattern and the initial part of the text.
Compare the hash values. If they match, check for character-by-character equality.
If the pattern is found, return its starting index in the text.
Slide the pattern along the text and repeat steps 2-4 until the end of the text.

Example 1 💡

Let's consider a pattern "ATTACK" and a text "DEFEND THE WALL FROM THE NORTH ATTACK".

java

import java.math.BigInteger;
import java.util.Arrays;

public class RabinKarp {
    // ... (Code for power function and hash function omitted for brevity)

    public static void main(String[] args) {
        String text = "DEFEND THE WALL FROM THE NORTH ATTACK";
        String pattern = "ATTACK";

        int[] patternHash = getPatternHash(pattern);
        int[] textHash = getTextHash(text, pattern.length());

        for (int i = pattern.length(); i <= text.length(); i++) {
            if (Arrays.equals(patternHash, Arrays.copyOfRange(textHash, i - pattern.length(), i))) {
                int possibleStartIndex = i - pattern.length();
                if (isPatternMatched(pattern, text, possibleStartIndex)) {
                    System.out.println("Found at index: " + possibleStartIndex);
                }
            }
            shiftTextHash(text, pattern.length());
        }
    }

    // ... (Code for isPatternMatched and shiftTextHash functions omitted for brevity)

    // Helper functions for calculating pattern hash, text hash, and shifting text hash
    private static int[] getPatternHash(String pattern) {
        int[] hashValues = new int[pattern.length()];
        hashValues[0] = pattern.charAt(0);
        BigInteger bigIntegerPattern = BigInteger.valueOf(hashValues[0]);
        for (int i = 1; i < pattern.length(); i++) {
            bigIntegerPattern = bigIntegerPattern.multiply(BigInteger.valueOf(10));
            bigIntegerPattern = bigIntegerPattern.add(BigInteger.valueOf(pattern.charAt(i)));
            hashValues[i] = bigIntegerPattern.intValue();
        }
        return hashValues;
    }

    private static int[] getTextHash(String text, int patternLength) {
        int[] hashValues = new int[text.length() - patternLength + 1];
        hashValues[0] = getHash(text.substring(0, patternLength));
        for (int i = 1; i < hashValues.length; i++) {
            hashValues[i] = getHash(text.substring(i, i + patternLength)) - getHash(text.substring(i - 1, i));
        }
        return hashValues;
    }

    private static int getHash(String str) {
        int[] hashValues = new int[str.length()];
        BigInteger bigInteger = BigInteger.valueOf(hashValues[0]);
        for (int i = 1; i < str.length(); i++) {
            bigInteger = bigInteger.multiply(BigInteger.valueOf(10));
            bigInteger = bigInteger.add(BigInteger.valueOf(str.charAt(i)));
            hashValues[i] = bigInteger.intValue();
        }
        return hashValues[hashValues.length - 1];
    }

    private static void shiftTextHash(String text, int patternLength) {
        int[] textHash = new int[text.length() - patternLength + 1];
        for (int i = 0; i < textHash.length; i++) {
            textHash[i] = textHash[i + 1] - getHash(text.substring(i, i + patternLength)) + (i == 0 ? 0 : -getHash(text.substring(i - 1, i)));
        }
    }
}

Example 2 💡

Let's consider a pattern "banana" and a text "apple banana apple apple banana apple".

java

import java.math.BigInteger;
import java.util.Arrays;

public class RabinKarp {
    // ... (Code for power function and hash function omitted for brevity)

    public static void main(String[] args) {
        String text = "apple banana apple apple banana apple";
        String pattern = "banana";

        int[] patternHash = getPatternHash(pattern);
        int[] textHash = getTextHash(text, pattern.length());

        for (int i = pattern.length(); i <= text.length(); i++) {
            if (Arrays.equals(patternHash, Arrays.copyOfRange(textHash, i - pattern.length(), i))) {
                int possibleStartIndex = i - pattern.length();
                if (isPatternMatched(pattern, text, possibleStartIndex)) {
                    System.out.println("Found at index: " + possibleStartIndex);
                }
            }
            shiftTextHash(text, pattern.length());
        }
    }

    // ... (Code for isPatternMatched and shiftTextHash functions omitted for brevity)

    // Helper functions for calculating pattern hash, text hash, and shifting text hash
    private static int[] getPatternHash(String pattern) {
        int[] hashValues = new int[pattern.length()];
        hashValues[0] = pattern.charAt(0);
        BigInteger bigIntegerPattern = BigInteger.valueOf(hashValues[0]);
        for (int i = 1; i < pattern.length(); i++) {
            bigIntegerPattern = bigIntegerPattern.multiply(BigInteger.valueOf(10));
            bigIntegerPattern = bigIntegerPattern.add(BigInteger.valueOf(pattern.charAt(i)));
            hashValues[i] = bigIntegerPattern.intValue();
        }
        return hashValues;
    }

    private static int[] getTextHash(String text, int patternLength) {
        int[] hashValues = new int[text.length() - patternLength + 1];
        hashValues[0] = getHash(text.substring(0, patternLength));
        for (int i = 1; i < hashValues.length; i++) {
            hashValues[i] = getHash(text.substring(i, i + patternLength)) - getHash(text.substring(i - 1, i));
        }
        return hashValues;
    }

    private static int getHash(String str) {
        int[] hashValues = new int[str.length()];
        BigInteger bigInteger = BigInteger.valueOf(hashValues[0]);
        for (int i = 1; i < str.length(); i++) {
            bigInteger = bigInteger.multiply(BigInteger.valueOf(10));
            bigInteger = bigInteger.add(BigInteger.valueOf(str.charAt(i)));
            hashValues[i] = bigInteger.intValue();
        }
        return hashValues[hashValues.length - 1];
    }

    private static void shiftTextHash(String text, int patternLength) {
        int[] textHash = new int[text.length() - patternLength + 1];
        for (int i = 0; i < textHash.length; i++) {
            textHash[i] = textHash[i + 1] - getHash(text.substring(i, i + patternLength)) + (i == 0 ? 0 : -getHash(text.substring(i - 1, i)));
        }
    }
}

Quiz 🎯

By the end of this tutorial, you should have a solid understanding of the Rabin-Karp algorithm and be able to implement it in your own projects. Happy coding! 💻🚀