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 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	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 java.lang.Object
clone, equals, 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