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:

Go to the source code of this file.

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 ()
size_t	kmp (const std::string &pattern, const std::string &text)
	KMP algorithm to find a pattern in a text.

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

Definition in file knuth_morris_pratt.cpp.

Function Documentation

kmp()

size_t string_search::kmp	(	const std::string &	pattern,
		const std::string &	text )

KMP algorithm to find a pattern in a text.

Parameters

pattern	string pattern to search
text	text in which to search

Returns

the starting index of the pattern if found

std::string::npos if not found

Definition at line 53 of file knuth_morris_pratt.cpp.

                                                            {
    if (pattern.empty()) {
        return 0;
    }
    std::vector<size_t> failure = getFailureArray(pattern);
    size_t text_length = text.size();
    size_t pattern_length = pattern.size();
    size_t k = 0;
    for (size_t j = 0; j < text_length; j++) {
        while (k != std::string::npos && pattern[k] != text[j]) {
            k = failure[k];
        }
        if (++k == pattern_length) {
            return j - k + 1;
        }
    }
    return std::string::npos;
}

main()

int main

(

void

)

Definition at line 95 of file knuth_morris_pratt.cpp.

           {
    tests();
    return 0;
}

tests()

void tests ( )

static

self-test implementations

Returns

void

Definition at line 79 of file knuth_morris_pratt.cpp.

                    {
    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";
}