edu.princeton.cs.algs4

Class KMP

java.lang.Object

edu.princeton.cs.algs4.KMP

public class KMP
extends java.lang.Object

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

This implementation uses a version of the Knuth-Morris-Pratt substring search algorithm. The version takes time proportional to n + m R in the worst case, where n is the length of the text string, m is the length of the pattern, and R is the alphabet size. It uses extra space proportional to m R.

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

Constructor Summary

Constructors

Constructor and Description
KMP(char[] pattern, int R) Preprocesses the pattern string.
KMP(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

KMP

public KMP(java.lang.String pat)

Preprocesses the pattern string.

Parameters:

pat - the pattern string

KMP

public KMP(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