Class RabinKarp

java.lang.Object

RabinKarp

public class RabinKarp
extends java.lang.Object

This class implements the Rabin-Karp algorithm to search for an occurrence of a given string pat in a given string txt. (The first string is called pattern, the second is called text.) The Rabin-Karp algorithm is probabilistic: in its Monte Carlo version, it may return a wrong answer (with a very low probability); in its Las Vegas version, it always return a correct answer but may not run in linear time (with very low probability).

An example of output of the teste client:

  % java RabinKarp abracadabra abacadabrabracabracadabrabrabracad
  pattern: abracadabra
  text:    abacadabrabracabracadabrabrabracad 
  match:                 abracadabra          
  

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

Constructor Summary

Constructors

Constructor and Description
RabinKarp(int R, char[] pattern) Not supported yet.
RabinKarp(java.lang.String pat) Constructs a RabinKarp object for the extended ASCII alphabet and a pattern pat given by a string.

Method Summary

Methods

Modifier and Type	Method and Description
static void	main(java.lang.String[] args) Test client.
int	search(java.lang.String txt) Returns the starting index of the first (exact) occurrence of the pattern in txt.

Methods inherited from class java.lang.Object

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

Constructor Detail

RabinKarp

public RabinKarp(int R,
         char[] pattern)

Not supported yet. Should construct a RabinKarp object for an R-character alphabet and a pattern given by a character array.

RabinKarp

public RabinKarp(java.lang.String pat)

Constructs a RabinKarp object for the extended ASCII alphabet and a pattern pat given by a string.

Method Detail

search

public int search(java.lang.String txt)

Returns the starting index of the first (exact) occurrence of the pattern in txt. This is the Las Vegas version; for the Monte Carlo version, must replace "check(txt, offset)" by "check(offset)" in the code.

main

public static void main(java.lang.String[] args)

Test client. Examples of output:

  % java RabinKarp abracadabra abacadabrabracabracadabrabrabracad
  pattern: abracadabra
  text:    abacadabrabracabracadabrabrabracad 
  match:                 abracadabra          

  % java RabinKarp rab abacadabrabracabracadabrabrabracad
  pattern: rab
  text:    abacadabrabracabracadabrabrabracad 
  match:           rab                         

  % java RabinKarp bcara abacadabrabracabracadabrabrabracad
  pattern: bcara
  text:         abacadabrabracabracadabrabrabracad 

  %  java RabinKarp rabrabracad abacadabrabracabracadabrabrabracad
  text:    abacadabrabracabracadabrabrabracad
  pattern:                        rabrabracad

  % java RabinKarp abacad abacadabrabracabracadabrabrabracad
  text:    abacadabrabracabracadabrabrabracad
  pattern: abacad