Describe the Rabin-Karp algorithm and its use in string searching.?

The Rabin-Karp algorithm is a string searching algorithm that is used to find a pattern within a larger text. It is an efficient algorithm for large texts as it only requires a constant amount of memory, making it ideal for certain applications.

The algorithm works by using a hash function to calculate the hash values of the pattern and the substrings of the text. The hash function used is a rolling hash function, which means that it updates the hash value of a substring in constant time as the substring is shifted by one character.

The Rabin-Karp algorithm then compares the hash values of the pattern and the substrings of the text. If the hash values match, the algorithm checks the pattern and the substring character by character to verify if they are identical. If they match, then the algorithm returns the starting index of the pattern within the text.

The Rabin-Karp algorithm can be implemented using different hash functions, such as the polynomial hash function or the prime hash function. The prime hash function is preferred over the polynomial hash function as it is less likely to produce hash collisions.

The time complexity of the Rabin-Karp algorithm is O(n+m), where n is the length of the text and m is the length of the pattern. However, in the worst case, the algorithm can have a time complexity of O(nm), which occurs when all the hash values of the substrings match the hash value of the pattern, and the algorithm has to verify each match character by character.

An example of the Rabin-Karp algorithm is as follows:

// Rabin-Karp algorithm implementation in Java

public class RabinKarp {
    public static int rabinKarp(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int p = 31;  // prime number used for hash function
        int mod = 1000000007;  // modulus used for hash function
        int power = 1;
        int patternHash = 0;
        int[] prefixHash = new int[n+1];

        // calculate the hash value of the pattern
        for (int i = 0; i < m; i++) {
            patternHash = (patternHash + (pattern.charAt(i)-'a'+1) * power) % mod;
            power = (power * p) % mod;
        }

        // calculate the prefix hash values of the text
        for (int i = 0; i < n; i++) {
            prefixHash[i+1] = (prefixHash[i] + (text.charAt(i)-'a'+1) * power) % mod;
            power = (power * p) % mod;
        }

        // check for matches between the pattern and the substrings of the text
        for (int i = 0; i <= n-m; i++) {
            int currentHash = (prefixHash[i+m] - prefixHash[i] + mod) % mod;
            if (currentHash == patternHash && text.substring(i, i+m).equals(pattern)) {
                return i;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        String text = "abcbcabcabcabcbcabccbacbabcbcabccbacbabcbcabccbacbabcbcabc"
                              + "cbacbabcbcabccbacbabcbcabccbacbabcbcabccbacb";
        String pattern = "bacb";
        int index = rabinKarp(text, pattern);
        if (index != -1) {
            System.out.println("Pattern found at index " + index);
        } else {
            System.out.println("Pattern not found");
        }
    }
}