WikiGalaxy
Z Algorithm
Introduction to Z Algorithm:
The Z Algorithm is a linear time string matching algorithm that is used to find all occurrences of a pattern in a given text. It works by creating a Z-array, where each element at index i represents the length of the longest substring starting from the position i in the string that matches the prefix of the string.
Example 1: Basic Pattern Matching
Understanding Z-array:
Consider the string "abacabadabacaba". The Z-array for this string helps in identifying the repeated patterns by comparing each suffix with the prefix.
public class ZAlgorithm {
public static int[] calculateZ(String s) {
int n = s.length();
int[] Z = new int[n];
int L = 0, R = 0;
for (int i = 1; i < n; ++i) {
if (i <= R)
Z[i] = Math.min(R - i + 1, Z[i - L]);
while (i + Z[i] < n && s.charAt(Z[i]) == s.charAt(i + Z[i]))
++Z[i];
if (i + Z[i] - 1 > R) {
L = i;
R = i + Z[i] - 1;
}
}
return Z;
}
public static void main(String[] args) {
String text = "abacabadabacaba";
int[] Z = calculateZ(text);
System.out.println(Arrays.toString(Z));
}
}
Console Output:
[0, 0, 1, 0, 3, 0, 1, 0, 7, 0, 1, 0, 3, 0, 1]
Example 2: Searching for a Pattern
Pattern Matching Using Z Algorithm:
To search for a pattern "aba" in a text "abacabadabacaba", we concatenate the pattern and the text with a special character in between and compute the Z-array.
public class ZPatternSearch {
public static void searchPattern(String pattern, String text) {
String concat = pattern + "$" + text;
int[] Z = calculateZ(concat);
for (int i = 0; i < Z.length; ++i) {
if (Z[i] == pattern.length()) {
System.out.println("Pattern found at index " + (i - pattern.length() - 1));
}
}
}
public static void main(String[] args) {
String pattern = "aba";
String text = "abacabadabacaba";
searchPattern(pattern, text);
}
}
Console Output:
Pattern found at index 0
Pattern found at index 4
Pattern found at index 8
Pattern found at index 12
Example 3: Longest Prefix Suffix
Finding Longest Prefix Suffix:
The Z-array can be used to find the longest prefix which is also a suffix in the string. This can be useful in various string processing tasks.
public class LongestPrefixSuffix {
public static int longestPrefixSuffix(String s) {
int[] Z = calculateZ(s);
int maxZ = 0;
for (int i = 1; i < Z.length; ++i) {
if (i + Z[i] == s.length()) {
maxZ = Math.max(maxZ, Z[i]);
}
}
return maxZ;
}
public static void main(String[] args) {
String s = "abacabadabacaba";
System.out.println("Longest Prefix Suffix Length: " + longestPrefixSuffix(s));
}
}
Console Output:
Longest Prefix Suffix Length: 7
Example 4: Handling Special Characters
Working with Special Characters:
The Z Algorithm can effectively handle strings with special characters. Consider a string with mixed characters and see how the Z-array is computed.
public class SpecialCharZAlgorithm {
public static void main(String[] args) {
String text = "a#b$c%a^b&c*";
int[] Z = calculateZ(text);
System.out.println(Arrays.toString(Z));
}
}
Console Output:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Example 5: Real-Time Applications
Applications in Real-Time Scenarios:
The Z Algorithm is used in bioinformatics for DNA sequencing, where it helps in identifying patterns in genetic sequences efficiently.
public class BioinformaticsApplication {
public static void main(String[] args) {
String dnaSequence = "AGCTAGCAGCTAGCTA";
String pattern = "AGCT";
searchPattern(pattern, dnaSequence);
}
}
Console Output:
Pattern found at index 0
Pattern found at index 5
Pattern found at index 10
