Z Algorithm Implementation in C++

By UDDESHYA PANKAJ

Z Algorithm is a pretty fast Pattern Matching Algorithm. It searches for a pattern in a text, and its time complexity is O(m+n). I have implemented the Z-algorithm in c++.

 

This algorithm is named Z Algorithm because, in this algorithm, we need to create a Z array or Z function.

It's the same as the KMP pattern matching algorithm in terms of complexity but it is easier to understand.

It is denoted as Z(k), where k is the index and Z(k) means the length of the longest substring starting at k which is also the prefix of the string.

As we can see in the above image that there is a string text and a pattern and we have found that pattern in that text (i.e know the index ).

 

So, to achieve the above task, what we will is that we will create a new string named str by concatenating (pattern + "$" + text).

Now we will create the Z array of size of str.

Initially, we will assign all the values of the Z array to zero.

 

Then we will be looping through the string (str) and checking for a match with the previous travelled index values.

If there is a match we will be returning the index of matched string in the original Text.

 

So, this how the Z Algorithm works, and its Time Complexity is O(m+n).

where m is the length of text and n is the length of the pattern. 

It's a very efficient Algorithm.