KMP (Algorithms 4/e)

Object
- edu.princeton.cs.algs4.KMP

```
public class KMP
extends 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(String pat)
Preprocesses the pattern string.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`static void`	`main(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 occurrence of the pattern string in the text string.
`int`	`search(String txt)` Returns the index of the first occurrence of the pattern string in the text string.

Methods inherited from class Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - KMP
```
public KMP(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(String txt)
```
    Returns the index of the first occurrence 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 occurrence 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(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