Class RabinKarp


  • public class RabinKarp
    extends Object
    The RabinKarp class finds the first occurrence of a pattern string in a text string.

    This implementation uses the Rabin-Karp algorithm.

    For additional documentation, see Section 5.3 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    • Constructor Detail

      • RabinKarp

        public RabinKarp​(char[] pattern,
                         int R)
        Preprocesses the pattern string.
        Parameters:
        pattern - the pattern string
        R - the alphabet size
      • RabinKarp

        public RabinKarp​(String pat)
        Preprocesses the pattern string.
        Parameters:
        pat - the pattern string
    • Method Detail

      • search

        public int search​(String txt)
        Returns the index of the first occurrence of the pattern string in the text string.
        Parameters:
        txt - the text string
        Returns:
        the index of the first occurrence of the pattern string in the text string; n if no such match
      • main

        public static void main​(String[] args)
        Takes a pattern string and an input string as command-line arguments; searches for the pattern string in the text string; and prints the first occurrence of the pattern string in the text string.
        Parameters:
        args - the command-line arguments