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

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d3/d80/z__function_8cpp.html below:

TheAlgorithms/C++: strings/z_function.cpp File Reference

The Z function for finding occurences of a pattern within a piece of text with time and space complexity O(n + m) More...

#include <cstdint>
#include <iostream>
#include <cstring>
#include <cassert>
#include <vector>

Go to the source code of this file.

The Z function for finding occurences of a pattern within a piece of text with time and space complexity O(n + m)

1. The Z-function for a string is an array of length n where the i-th element is equal to the greatest number of characters starting from the position i that coincide with the first characters of s.
2. E.g.: string: ababb then z[2]=2 as s[2]=s[0] and s[3]=s[1] and s[4]!=s[2]

Definition in file z_function.cpp.

Using Z_function to find a pattern in a text.

Parameters

[in] pattern string pattern to search [in] text text in which to search

Returns

a vector of starting indexes where pattern is found in the text

Definition at line 54 of file z_function.cpp.

55 {

56 uint64_t text_length = text.size(), pattern_length = pattern.size();

std::vector<uint64_t> z =

(pattern +

+ text);

58 std::vector<uint64_t> matching_indexes;

59

60 for (uint64_t i = 0; i < text_length; i++) {

61 if (z[i + pattern_length + 1] == pattern_length) {

62 matching_indexes.push_back(i);

63 }

64 }

65 return matching_indexes;

66}

std::vector< uint64_t > Z_function(const std::string &pattern)

for IO operations

Main function.

Returns

0 on exit

Definition at line 110 of file z_function.cpp.

110 {

112 return 0;

113}

static void test()

Self-test implementations.

Self-test implementations.

Returns

void

Definition at line 72 of file z_function.cpp.

72 {

73

74 std::string text1 = "alskfjaldsabc1abc1abcbksbcdnsdabcabc";

75 std::string pattern1 = "abc";

76

77

std::vector<uint64_t> matching_indexes1 =

(pattern1, text1);

79 assert((matching_indexes1 == std::vector<uint64_t>{10, 14, 18, 30, 33}));

80

81

82 std::string text2 = "greengrass";

83 std::string pattern2 = "abc";

84

85

std::vector<uint64_t> matching_indexes2 =

(pattern2, text2);

87 assert((matching_indexes2 == std::vector<uint64_t>{}));

88

89

90 std::string text3 = "";

91 std::string pattern3 = "abc";

92

93

std::vector<uint64_t> matching_indexes3 =

(pattern3, text3);

95 assert((matching_indexes3 == std::vector<uint64_t>{}));

96

97

98 std::string text4 = "redsand";

99 std::string pattern4 = "";

100

101

std::vector<uint64_t> matching_indexes4 =

(pattern4, text4);

103 assert((matching_indexes4 == std::vector<uint64_t>{0, 1, 2, 3, 4, 5, 6}));

104}

std::vector< uint64_t > find_pat_in_text(const std::string &pattern, const std::string &text)

Using Z_function to find a pattern in a text.

for IO operations

for string for assert for std::vector

Generate the Z-function for the inputted string.

Parameters

[in] pattern text on which to apply the Z-function

Returns

the Z-function output as a vector array

Definition at line 29 of file z_function.cpp.

29 {

30 uint64_t pattern_length = pattern.size();

31 std::vector<uint64_t> z(pattern_length, 0);

32

33 for (uint64_t i = 1, l = 0, r = 0; i < pattern_length; i++) {

34 if (i <= r) {

35 z[i] = std::min(r - i + 1, z[i - l]);

36 }

37 while (i + z[i] < pattern_length &&

38 pattern[z[i]] == pattern[i + z[i]]) {

39 z[i]++;

40 }

41 if (i + z[i] - 1 > r) {

42 r = i + z[i] - 1;

43 }

44 }

45 return z;

46}

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