This directory contains sample C++ code for an implementation of the Knuth-Morris-Pratt linear time string matching algorithm, and an example program that uses this algorithm to search for paragraphs containing a given string (similar to grep).
Files in this directory:
Arguments to the class constructor are the the string to be searched for and an optional length (-1 if the string is null-terminated); the constructor implements the preprocessing stage of the KMP algorithm.
The function string_match.reset() begins searching for a match, after which the function string_match.match(char c) processes one more character of text, implementing the scanning stage of the KMP algorithm and returning a Boolean value, true if the character processed was the last character of a match.
string_match m("nano"); m.reset(); for (char * s = "banananobano", *s != '\0'; s++) if (m.match(*s)) printf("found a nano!\n");
ICS 161 --
Dept. Information & Computer Science --