kmp
Class TextBookKMPMatcher

java.lang.Object
  kmp.TextBookKMPMatcher

public class TextBookKMPMatcher
extends java.lang.Object

A TextBookKMPMatcher is a KMP matcher using modified code from the Cormen, Leiserson, Rivest, and Stein textbook "Introductuction to Algorithms", 3rd edition. The textbook code is modified in two ways:

• The textbook code prints a statement when a match is found. The TextBookKMPMatcher is given an iterator interface. After the text is set by invoking setText(), a client retrieves match positions by invoking nextMatch() until -1 is returned.
• Textbook variable names have been changed to more meaningful names. These names are more suggestive of the loop invariants.

This code will not work. The textbook code is designed assuming that array indexing starts at 1. The code needs to be modified for array indexing that starts at 0.

Constructor Summary

TextBookKMPMatcher(java.lang.String pattern)
new KMPMatcher(pattern) returns a string matcher for pattern.

Method Summary

void	createPrefixFunction() createPrefixFunction() creates the prefix function for pattern.
int	nextMatch() kmp.nextMatch() returns the position of the next match for kmp's pattern in kmp's text.
void	setText(java.lang.String text) kmp.setText(text) sets the text for kmp to text.

Methods inherited from class java.lang.Object

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

Constructor Detail

TextBookKMPMatcher

public TextBookKMPMatcher(java.lang.String pattern)

new KMPMatcher(pattern) returns a string matcher for pattern. The pattern argument must be a non-empty string.

Parameters:

pattern - the pattern

Throws:

java.lang.IllegalArgumentException - if pattern is null or empty

Method Detail

createPrefixFunction

private void createPrefixFunction()

createPrefixFunction() creates the prefix function for pattern. The prefix function values are held in the array prefixFunction. prefixFunction[i] is the size of the largest proper suffix of the first i characters of pattern that is also a prefix of pattern.

setText

public void setText(java.lang.String text)

kmp.setText(text) sets the text for kmp to text.

Parameters:

text - the text

nextMatch

public int nextMatch()

kmp.nextMatch() returns the position of the next match for kmp's pattern in kmp's text. A return value of -1 signals that there are no more matches.

Returns:

the position of the next match