| KMP Class |
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 as space 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.
Inheritance HierarchyNamespace: Algs4Net
Assembly: Algs4Net (in Algs4Net.dll) Version: 1.0.0.0 (1.0.0.0)
SyntaxC#
public class KMP
The KMP type exposes the following members.
Constructors| Name | Description | |
|---|---|---|
 | KMP(String) | Preprocesses the pattern string. |
| KMP(Char, Int32) | Preprocesses the pattern string. |
Methods| Name | Description | |
|---|---|---|
 | MainTest |
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. |
| Search(Char) |
Returns the index of the first occurrrence of the pattern string
in the text string. |
| Search(String) |
Returns the index of the first occurrrence of the pattern string
in the text string. |
RemarksFor additional documentation, see Section 5.3 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
This class is a C# port from the original Java class KMP implementation by the respective authors.
See Also