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 <cassert>
#include <iostream>
#include <string>
#include <vector>

Include dependency graph for knuth_morris_pratt.cpp:

Namespaces
namespace	string_search
	String search algorithms.

Functions
std::vector< size_t >	string_search::getFailureArray (const std::string &pattern)
	Generate the partial match table aka failure function for a pattern to search.
size_t	string_search::kmp (const std::string &pattern, const std::string &text)
	KMP algorithm to find a pattern in a text.
static void	tests ()
	self-test implementations
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

   Author

   Yancey

Function Documentation

main()

int main

(

void

)

           {
    tests();
    return 0;
}

tests()

static void tests ( )

static

self-test implementations

Returns

void

                    {
    assert(kmp("abc1abc12l", "alskfjaldsabc1abc1abc12k2") == std::string::npos);
    assert(kmp("bca", "abcabc") == 1);
    assert(kmp("World", "helloWorld") == 5);
    assert(kmp("c++", "his_is_c++") == 7);
    assert(kmp("happy", "happy_coding") == 0);
    assert(kmp("", "pattern is empty") == 0);
 
    // this lets the user know that the tests have passed
    std::cout << "All KMP algorithm tests have successfully passed!\n";
}