Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
knuth_morris_pratt.cpp File Reference

The Knuth-Morris-Pratt Algorithm for finding a pattern within a piece of text with complexity O(n + m) More...

#include <iostream>
#include <cstring>
#include <vector>
Include dependency graph for knuth_morris_pratt.cpp:

Namespaces

 

Functions

std::vector< int > string_search::getFailureArray (const std::string &pattern)
 
bool string_search::kmp (const std::string &pattern, const std::string &text)
 
int main ()
 

Detailed Description

The Knuth-Morris-Pratt Algorithm for finding a pattern within a piece of text with complexity O(n + m)

  1. 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.
  2. 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

Function Documentation

◆ main()

int main ( void  )

Main function

76  {
77  std::string text = "alskfjaldsabc1abc1abc12k23adsfabcabc";
78  std::string pattern = "abc1abc12l";
79 
80  if (kmp(pattern, text) == true) {
81  std::cout << "Found" << std::endl;
82  } else {
83  std::cout << "Not Found" << std::endl;
84  }
85 
86  text = "abcabc";
87  pattern = "bca";
88  if (kmp(pattern, text) == true) {
89  std::cout << "Found" << std::endl;
90  } else {
91  std::cout << "Not Found" << std::endl;
92  }
93 
94  return 0;
95 }
Here is the call graph for this function:
std::string
STL class.
std::cout
string_search::kmp
bool kmp(const std::string &pattern, const std::string &text)
Definition: knuth_morris_pratt.cpp:56
std::endl
T endl(T... args)