edu.princeton.cs.algs4

Class BoyerMoore

java.lang.Object

edu.princeton.cs.algs4.BoyerMoore

public class BoyerMoore
extends java.lang.Object

The BoyerMoore class finds the first occurrence of a pattern string in a text string.

This implementation uses the Boyer-Moore algorithm (with the bad-character rule, but not the strong good suffix rule).

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

Constructor Summary

Constructors

Constructor and Description
BoyerMoore(char[] pattern, int R) Preprocesses the pattern string.
BoyerMoore(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(char[] text) Returns the index of the first occurrrence 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

BoyerMoore

public BoyerMoore(java.lang.String pat)

Preprocesses the pattern string.

Parameters:

pat - the pattern string

BoyerMoore

public BoyerMoore(char[] pattern,
                  int R)

Preprocesses the pattern string.

Parameters:

pattern - the pattern string

R - the alphabet size

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

search

public int search(char[] text)

Returns the index of the first occurrrence of the pattern string in the text string.

Parameters:

text - 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