Z algorithm in C++

In this blog, we will mainly discuss the concept of the z algorithm in C++. This algorithm is also similar to the concept of the KMP algorithm.

Both KMP and z algorithms are basically a string algorithm. These algorithms are used for string matching purposes.

In comparison, the z algorithm is more practically easy to code than the KMP algorithm.

Program: Z algorithm in C++

In this blog, we will discuss see how to code the concept of z algorithm using C++ language.

let’s start, the very initial thing which we require is two strings. The pattern string and the actual text string from where we have to match the pattern.

 

Both the strings which are initially required are demonstrated below:

 

 string str = "ababaa"; 
 string ptrn = "aba";

Now, in order to do further processing to match the strings, we will now merge both the strings with a special character in between both the strings because it will act as a separator. The special characters which we are using in our case are “#”.

Below is the actual code of the z algorithm using c++

 

#include <iostream>
using namespace std;

int main() {
  string str = "ababaa"; 
    string ptrn = "aba";
    string cat_str= ptrn+"#"+str;
    
    //calculate length of cat_str
    int n=cat_str.length();
    
    // initialise a integer array of cat_str length 
    int z_index[n];
    
    //initialise 3 integers for indexing in loop
  
    int x, y, k; 
    x = y = 0; 
    for (int i = 1; i < n; ++i) 
    { 
        if (i > y) 
        { 
            x = y = i; 
            while (y<n && cat_str[y-x] == cat_str[y]) 
                y++; 
            z_index[i] = y-x; 
            y--; 
        } 
        else
        { 
            k = i-x; 
            if (z_index[k] < y-i+1) 
                z_index[i] = z_index[k]; 
            else
            { 
                x = i; 
                while (y<n && cat_str[y-x] == cat_str[y]) 
                    y++; 
                z_index[i] = y-x; 
                y--; 
            } 
        } 
    } 
    
    for (int i = 0; i < n; ++i) 
    { 
        
        if (z_index[i] == ptrn.length()) 
            cout << "Pattern is found at index "
                << i - ptrn.length() -1 << endl; 
    } 
    return 0;
    
}

 

Output:
Pattern is found at index 0
Pattern is found at index 2

 

I hope I have made the concept clear.

Please let me know if there is anything that isn’t clear.

You may also learn about :

Thank You.

Leave a Reply

Your email address will not be published. Required fields are marked *