The Knuth-Morris-Pratt Algorithm for finding a pattern within a piece of text with complexity O(n + m)
More...
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
The Knuth-Morris-Pratt Algorithm for finding a pattern within a piece of text with complexity O(n + m)
- Preprocess pattern to identify any suffixes that are identical to prefixes. This tells us where to continue from if we get a mismatch between a character in our pattern and the text.
- Step through the text one character at a time and compare it to a character in the pattern updating our location within the pattern if necessary
- Author
- Yancey
◆ main()
95 {
97 return 0;
98}
static void tests()
self-test implementations
Definition knuth_morris_pratt.cpp:79
◆ tests()
self-test implementations
- Returns
- void
79 {
80 assert(kmp("abc1abc12l", "alskfjaldsabc1abc1abc12k2") == std::string::npos);
81 assert(kmp("bca", "abcabc") == 1);
82 assert(kmp("World", "helloWorld") == 5);
83 assert(kmp("c++", "his_is_c++") == 7);
84 assert(kmp("happy", "happy_coding") == 0);
85 assert(kmp("", "pattern is empty") == 0);
86
87
88 std::cout <<
"All KMP algorithm tests have successfully passed!\n";
89}