Z algorithm in Java
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
Leave a Reply