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>

Include dependency graph for z_function.cpp:

Go to the source code of this file.

Functions
std::vector< uint64_t >	Z_function (const std::string &pattern)
	for IO operations
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.
static void	test ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

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]

   Author

   Ritika Gupta

Definition in file z_function.cpp.

Function Documentation

find_pat_in_text()

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.

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.

                                                              {
    uint64_t text_length = text.size(), pattern_length = pattern.size();
    std::vector<uint64_t> z = Z_function(pattern + '#' + text);
    std::vector<uint64_t> matching_indexes;
 
    for (uint64_t i = 0; i < text_length; i++) {
        if (z[i + pattern_length + 1] == pattern_length) {
            matching_indexes.push_back(i);
        }
    }
    return matching_indexes;
}

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 110 of file z_function.cpp.

           {
    test();  // run self-test implementations
    return 0;
}

test()

void test ( )

static

Self-test implementations.

Returns

void

Definition at line 72 of file z_function.cpp.

                   {
    // usual case
    std::string text1 = "alskfjaldsabc1abc1abcbksbcdnsdabcabc";
    std::string pattern1 = "abc";
 
    // matching_indexes1 gets the indexes where pattern1 exists in text1
    std::vector<uint64_t> matching_indexes1 = find_pat_in_text(pattern1, text1);
    assert((matching_indexes1 == std::vector<uint64_t>{10, 14, 18, 30, 33}));
 
    // corner case
    std::string text2 = "greengrass";
    std::string pattern2 = "abc";
 
    // matching_indexes2 gets the indexes where pattern2 exists in text2
    std::vector<uint64_t> matching_indexes2 = find_pat_in_text(pattern2, text2);
    assert((matching_indexes2 == std::vector<uint64_t>{}));
 
    // corner case - empty text
    std::string text3 = "";
    std::string pattern3 = "abc";
 
    // matching_indexes3 gets the indexes where pattern3 exists in text3
    std::vector<uint64_t> matching_indexes3 = find_pat_in_text(pattern3, text3);
    assert((matching_indexes3 == std::vector<uint64_t>{}));
 
    // corner case - empty pattern
    std::string text4 = "redsand";
    std::string pattern4 = "";
 
    // matching_indexes4 gets the indexes where pattern4 exists in text4
    std::vector<uint64_t> matching_indexes4 = find_pat_in_text(pattern4, text4);
    assert((matching_indexes4 == std::vector<uint64_t>{0, 1, 2, 3, 4, 5, 6}));
}

Z_function()

std::vector< uint64_t > Z_function

(

const std::string &

pattern

)

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.

                                                         {
    uint64_t pattern_length = pattern.size();
    std::vector<uint64_t> z(pattern_length, 0);
 
    for (uint64_t i = 1, l = 0, r = 0; i < pattern_length; i++) {
        if (i <= r) {
            z[i] = std::min(r - i + 1, z[i - l]);
        }
        while (i + z[i] < pattern_length &&
               pattern[z[i]] == pattern[i + z[i]]) {
            z[i]++;
        }
        if (i + z[i] - 1 > r) {
            r = i + z[i] - 1;
        }
    }
    return z;
}