A RetroSearch Logo

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Search Query:

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/de/d6a/knuth__morris__pratt_8cpp_source.html below:

TheAlgorithms/C++: strings/knuth_morris_pratt.cpp Source File

Go to the documentation of this file. 33 size_t

pattern_length = pattern.size();

34

std::vector<size_t> failure(pattern_length + 1);

35

failure[0] = std::string::npos;

36 size_t

j = std::string::npos;

37 for

(

int

i = 0; i < pattern_length; i++) {

38 while

(j != std::string::npos && pattern[j] != pattern[i]) {

53size_t kmp

(

const

std::string &pattern,

const

std::string &text) {

54 if

(pattern.empty()) {

58 size_t

text_length = text.size();

59 size_t

pattern_length = pattern.size();

61 for

(

size_t

j = 0; j < text_length; j++) {

62 while

(k != std::string::npos && pattern[k] != text[j]) {

65 if

(++k == pattern_length) {

69 return

std::string::npos;

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);

88

std::cout <<

"All KMP algorithm tests have successfully passed!\n"

;

int main()

Main function.

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

KMP algorithm to find a pattern in a text.

static void tests()

self-test implementations

String search algorithms.

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

KMP algorithm to find a pattern in a text.

std::vector< size_t > getFailureArray(const std::string &pattern)

Generate the partial match table aka failure function for a pattern to search.

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4