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
namespace	string_search
	String search algorithms.

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

           {
    std::string text = "alskfjaldsabc1abc1abc12k23adsfabcabc";
    std::string pattern = "abc1abc12l";
 
    if (kmp(pattern, text) == true) {
        std::cout << "Found" << std::endl;
    } else {
        std::cout << "Not Found" << std::endl;
    }
 
    text = "abcabc";
    pattern = "bca";
    if (kmp(pattern, text) == true) {
        std::cout << "Found" << std::endl;
    } else {
        std::cout << "Not Found" << std::endl;
    }
 
    return 0;
}

Here is the call graph for this function: