edu.princeton.cs.algs4

Class RabinKarp

java.lang.Object

edu.princeton.cs.algs4.RabinKarp

public class RabinKarp
extends java.lang.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 Summary

Constructors

Constructor and Description
RabinKarp(char[] pattern, int R) Preprocesses the pattern string.
RabinKarp(java.lang.String pat) Preprocesses the pattern string.

Method Summary

Modifier and Type	Method and Description
static void	main(java.lang.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.
int	search(java.lang.String txt) Returns the index of the first occurrrence of the pattern string in the text string.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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(java.lang.String pat)

Preprocesses the pattern string.

Parameters:

pat - the pattern string

Method Detail

search

public int search(java.lang.String txt)

Returns the index of the first occurrrence 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(java.lang.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