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.