kmp
Class TextBookKMPMatcher

java.lang.Object
  extended by 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:

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