Z algorithm in Java

By Aakash Puri

In this tutorial, you will learn what is Z algorithm and how to implement it in Java Programming Language.

What is Z-Algorithm?

Z Algorithm is generally used to find a specific pattern (or substring) in a string. For instance, consider a string “abaccbab” and you want to search for pattern “ab”. You can observe that it is present at the 1st and 7th position of the string. Now let’s learn how to implement it in Java –

Step 1: Create a Z-array in Java

package javaapplication13;
public class JavaApplication13 {
     private static void Zarr(String str, int[] Z) { 
          int n = str.length(); 
            int l = 0, q = 0; 
  
        for(int i = 1; i < n; ++i) { 
            if(i > q){ 
  
                l = q = i; 
                while(q < n && str.charAt(q - l) == str.charAt(q)) 
                    q++; 
                  
                Z[i] = q - l; 
                q--; 
  
            } 
            else{ 
                  int k = i - l; 
                  if(Z[k] < q - i + 1) 
                    Z[i] = Z[k]; 
                  else{ 
                      l = i; 
                    while(q < n && str.charAt(q - l) == str.charAt(q)) 
                        q++; 
                      
                    Z[i] = q - l; 
                    q--; 
                } 
            } 
        } 
    } 
     
    

Step 2: Search for pattern

public static void search(String text, String pattern) 
    { 
        String concat = pattern + "$" + text; 
        int l = concat.length(); 
        int Z[] = new int[l]; 
        Zarr(concat, Z); 
        for(int i = 0; i < l; ++i){ 
           if(Z[i] == pattern.length()){ 
                System.out.println("Pattern at : "
                              + ((i+1) - pattern.length() - 1)); 
            } 
        } 
    }

Step 3: Call main() function in Z algorithm

 public static void main(String[] args)  
    { 
        String text = "abaccbab"; 
        String pattern = "ab"; 
  
        search(text, pattern); 
    } 
    
}

Output:-

Pattern at : 1
Pattern at : 7

Also read: Check if a number is Euler Pseudoprime in Java