public class KMP extends Object
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 and Description |
---|
KMP(char[] pattern,
int R)
Preprocesses the pattern string.
|
KMP(String pat)
Preprocesses the pattern string.
|
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.
|
public KMP(String pat)
pat
- the pattern stringpublic KMP(char[] pattern, int R)
pattern
- the pattern stringR
- the alphabet sizepublic int search(String txt)
txt
- the text stringpublic int search(char[] text)
text
- the text stringpublic static void main(String[] args)
args
- the command-line arguments