Z algorithm for pattern matching
The Z algorithm is a linear time string pattern matching algorithm. It is used to find all occurrences of a pattern in a given text in linear time. The algorithm is based on the Z-function, which is an array of integers representing the lengths of the longest common prefix between the pattern and each suffix of the text.
To compute the Z-function, the algorithm maintains two pointers, L and R, such that L<=R. Initially, L and R are set to the beginning of the string. At each step, the algorithm compares the characters at positions R and R-L with the corresponding characters in the pattern. If the characters match, the algorithm increments R and continues the comparison. If the characters do not match, the algorithm stops and computes the value of Z[i] as R-L, where i is the position being considered.
The algorithm then tries to extend the prefix of the text by moving L to i and R to the first character after R that does not match the pattern. The process is repeated until all positions in the text have been considered.
Once the Z-function has been computed, the pattern can be searched in the text by comparing the values of the Z-function with the length of the pattern. If a value of the Z-function is equal to the length of the pattern, it means that the pattern occurs at that position in the text.
Overall, the Z algorithm is a fast and efficient method for pattern matching and is widely used in many applications.
Here given code implementation process.
// Java program for
// Z algorithm for pattern matching
public class Matching
{
public void calculateZValue(String str, int n, int[] z)
{
int left = 0;
int right = 0;
int k = 0;
for (int i = 1; i < n; ++i)
{
if (i > right)
{
left = right = i;
while (right < n &&
str.charAt(right - left) == str.charAt(right))
{
right++;
}
z[i] = right - left;
right--;
}
else
{
k = i - left;
if (z[k] < right - i + 1)
{
z[i] = z[k];
}
else
{
left = i;
while (right < n &&
str.charAt(right - left) == str.charAt(right))
{
right++;
}
z[i] = right - left;
right--;
}
}
}
}
public void findPattern(String text, String pattern)
{
// Get the length of given text
int n = text.length();
// Get the length of given pattern
int m = pattern.length();
// Combine search pattern and given text
String data = pattern + text;
int k = data.length();
int[] z = new int[k];
calculateZValue(data, k, z);
for (int i = 0; i < k; i++)
{
if (z[i] == m)
{
System.out.println("Pattern found at index " + (i - m));
}
}
}
public static void main(String[] args)
{
Matching task = new Matching();
// Given text
String text = "LXYZHEQXYZXYZQQHE11HXYZ1E";
// Search pattern
String pattern = "XYZ";
// Find pattern which occurs in given text
/*
Text = LXYZHEQXYZXYZQQHE11HXYZ1E
Pattern = XYZ
--------------------------------
➀ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➁ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➂ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➃ LXYZHEQXYZXYZQQHE11HXYZ1E
---
*/
task.findPattern(text, pattern);
}
}Output
Pattern found at index 1
Pattern found at index 7
Pattern found at index 10
Pattern found at index 20// Include header file
#include <iostream>
#include <string>
using namespace std;
// C++ program for
// Z algorithm for pattern matching
class Matching
{
public: void calculateZValue(string str, int n, int z[])
{
int left = 0;
int right = 0;
int k = 0;
for (int i = 1; i < n; ++i)
{
if (i > right)
{
left = right = i;
while (right < n &&
str[right - left] == str[right])
{
right++;
}
z[i] = right - left;
right--;
}
else
{
k = i - left;
if (z[k] < right - i + 1)
{
z[i] = z[k];
}
else
{
left = i;
while (right < n &&
str[right - left] == str[right])
{
right++;
}
z[i] = right - left;
right--;
}
}
}
}
void findPattern(string text, string pattern)
{
// Get the length of given text
int n = text.length();
// Get the length of given pattern
int m = pattern.length();
// Combine search pattern and given text
string data = pattern + text;
int k = data.length();
int z[k];
this->calculateZValue(data, k, z);
for (int i = 0; i < k; i++)
{
if (z[i] == m)
{
cout << "Pattern found at index "
<< (i - m) << endl;
}
}
}
};
int main()
{
Matching *task = new Matching();
// Given text
string text = "LXYZHEQXYZXYZQQHE11HXYZ1E";
// Search pattern
string pattern = "XYZ";
// Find pattern which occurs in given text
/*
Text = LXYZHEQXYZXYZQQHE11HXYZ1E
Pattern = XYZ
--------------------------------
➀ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➁ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➂ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➃ LXYZHEQXYZXYZQQHE11HXYZ1E
---
*/
task->findPattern(text, pattern);
return 0;
}Output
Pattern found at index 1
Pattern found at index 7
Pattern found at index 10
Pattern found at index 20// Include namespace system
using System;
// Csharp program for
// Z algorithm for pattern matching
public class Matching
{
public void calculateZValue(String str, int n, int[] z)
{
int left = 0;
int right = 0;
int k = 0;
for (int i = 1; i < n; ++i)
{
if (i > right)
{
left = right = i;
while (right < n &&
str[right - left] == str[right])
{
right++;
}
z[i] = right - left;
right--;
}
else
{
k = i - left;
if (z[k] < right - i + 1)
{
z[i] = z[k];
}
else
{
left = i;
while (right < n &&
str[right - left] == str[right])
{
right++;
}
z[i] = right - left;
right--;
}
}
}
}
public void findPattern(String text, String pattern)
{
// Get the length of given text
int n = text.Length;
// Get the length of given pattern
int m = pattern.Length;
// Combine search pattern and given text
String data = pattern + text;
int k = data.Length;
int[] z = new int[k];
this.calculateZValue(data, k, z);
for (int i = 0; i < k; i++)
{
if (z[i] == m)
{
Console.WriteLine("Pattern found at index " + (i - m));
}
}
}
public static void Main(String[] args)
{
Matching task = new Matching();
// Given text
String text = "LXYZHEQXYZXYZQQHE11HXYZ1E";
// Search pattern
String pattern = "XYZ";
// Find pattern which occurs in given text
/*
Text = LXYZHEQXYZXYZQQHE11HXYZ1E
Pattern = XYZ
--------------------------------
➀ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➁ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➂ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➃ LXYZHEQXYZXYZQQHE11HXYZ1E
---
*/
task.findPattern(text, pattern);
}
}Output
Pattern found at index 1
Pattern found at index 7
Pattern found at index 10
Pattern found at index 20package main
import "fmt"
// Go program for
// Z algorithm for pattern matching
type Matching struct {}
func getMatching() * Matching {
var me *Matching = &Matching {}
return me
}
func(this Matching) calculateZValue(str string, n int, z[] int) {
var left int = 0
var right int = 0
var k int = 0
for i := 1 ; i < n ; i++ {
if i > right {
left = i
right = i
for (right < n && str[right - left] == str[right]) {
right++
}
z[i] = right - left
right--
} else {
k = i - left
if z[k] < right - i + 1 {
z[i] = z[k]
} else {
left = i
for (right < n && str[right - left] == str[right]) {
right++
}
z[i] = right - left
right--
}
}
}
}
func(this Matching) findPattern(text, pattern string) {
// Get the length of given pattern
var m int = len(pattern)
// Combine search pattern and given text
var data string = pattern + text
var k int = len(data)
var z = make([] int, k)
this.calculateZValue(data, k, z)
for i := 0 ; i < k ; i++ {
if z[i] == m {
fmt.Println("Pattern found at index ", (i - m))
}
}
}
func main() {
var task * Matching = getMatching()
// Given text
var text string = "LXYZHEQXYZXYZQQHE11HXYZ1E"
// Search pattern
var pattern string = "XYZ"
// Find pattern which occurs in given text
/*
Text = LXYZHEQXYZXYZQQHE11HXYZ1E
Pattern = XYZ
--------------------------------
➀ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➁ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➂ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➃ LXYZHEQXYZXYZQQHE11HXYZ1E
---
*/
task.findPattern(text, pattern)
}Output
Pattern found at index 1
Pattern found at index 7
Pattern found at index 10
Pattern found at index 20<?php
// Php program for
// Z algorithm for pattern matching
class Matching
{
public function calculateZValue($str, $n, &$z)
{
$left = 0;
$right = 0;
$k = 0;
for ($i = 1; $i < $n; ++$i)
{
if ($i > $right)
{
$left = $right = $i;
while ($right < $n &&
$str[$right - $left] == $str[$right])
{
$right++;
}
$z[$i] = $right - $left;
$right--;
}
else
{
$k = $i - $left;
if ($z[$k] < $right - $i + 1)
{
$z[$i] = $z[$k];
}
else
{
$left = $i;
while ($right < $n &&
$str[$right - $left] == $str[$right])
{
$right++;
}
$z[$i] = $right - $left;
$right--;
}
}
}
}
public function findPattern($text, $pattern)
{
// Get the length of given text
$n = strlen($text);
// Get the length of given pattern
$m = strlen($pattern);
// Combine search pattern and given text
$data = $pattern.$text;
$k = strlen($data);
$z = array_fill(0, $k, 0);
$this->calculateZValue($data, $k, $z);
for ($i = 0; $i < $k; $i++)
{
if ($z[$i] == $m)
{
echo("Pattern found at index ".($i - $m)."\n");
}
}
}
}
function main()
{
$task = new Matching();
// Given text
$text = "LXYZHEQXYZXYZQQHE11HXYZ1E";
// Search pattern
$pattern = "XYZ";
// Find pattern which occurs in given text
/*
Text = LXYZHEQXYZXYZQQHE11HXYZ1E
Pattern = XYZ
--------------------------------
➀ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➁ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➂ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➃ LXYZHEQXYZXYZQQHE11HXYZ1E
---
*/
$task->findPattern($text, $pattern);
}
main();Output
Pattern found at index 1
Pattern found at index 7
Pattern found at index 10
Pattern found at index 20// Node JS program for
// Z algorithm for pattern matching
class Matching
{
calculateZValue(str, n, z)
{
var left = 0;
var right = 0;
var k = 0;
for (var i = 1; i < n; ++i)
{
if (i > right)
{
left = right = i;
while (right < n &&
str.charAt(right - left) == str.charAt(right))
{
right++;
}
z[i] = right - left;
right--;
}
else
{
k = i - left;
if (z[k] < right - i + 1)
{
z[i] = z[k];
}
else
{
left = i;
while (right < n &&
str.charAt(right - left) == str.charAt(right))
{
right++;
}
z[i] = right - left;
right--;
}
}
}
}
findPattern(text, pattern)
{
// Get the length of given text
var n = text.length;
// Get the length of given pattern
var m = pattern.length;
// Combine search pattern and given text
var data = pattern + text;
var k = data.length;
var z = Array(k).fill(0);
this.calculateZValue(data, k, z);
for (var i = 0; i < k; i++)
{
if (z[i] == m)
{
console.log("Pattern found at index " + (i - m));
}
}
}
}
function main()
{
var task = new Matching();
// Given text
var text = "LXYZHEQXYZXYZQQHE11HXYZ1E";
// Search pattern
var pattern = "XYZ";
// Find pattern which occurs in given text
/*
Text = LXYZHEQXYZXYZQQHE11HXYZ1E
Pattern = XYZ
--------------------------------
➀ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➁ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➂ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➃ LXYZHEQXYZXYZQQHE11HXYZ1E
---
*/
task.findPattern(text, pattern);
}
main();Output
Pattern found at index 1
Pattern found at index 7
Pattern found at index 10
Pattern found at index 20# Python 3 program for
# Z algorithm for pattern matching
class Matching :
def calculateZValue(self, str, n, z) :
left = 0
right = 0
k = 0
i = 1
while (i < n) :
if (i > right) :
left = right = i
while (right < n and
str[right - left] == str[right]) :
right += 1
z[i] = right - left
right -= 1
else :
k = i - left
if (z[k] < right - i + 1) :
z[i] = z[k]
else :
left = i
while (right < n and
str[right - left] == str[right]) :
right += 1
z[i] = right - left
right -= 1
i += 1
def findPattern(self, text, pattern) :
# Get the length of given text
n = len(text)
# Get the length of given pattern
m = len(pattern)
# Combine search pattern and given text
data = pattern + text
k = len(data)
z = [0] * (k)
self.calculateZValue(data, k, z)
i = 0
while (i < k) :
if (z[i] == m) :
print("Pattern found at index ", (i - m))
i += 1
def main() :
task = Matching()
# Given text
text = "LXYZHEQXYZXYZQQHE11HXYZ1E"
# Search pattern
pattern = "XYZ"
# Find pattern which occurs in given text
# Text = LXYZHEQXYZXYZQQHE11HXYZ1E
# Pattern = XYZ
# --------------------------------
# ➀ LXYZHEQXYZXYZQQHE11HXYZ1E
# ---
# ➁ LXYZHEQXYZXYZQQHE11HXYZ1E
# ---
# ➂ LXYZHEQXYZXYZQQHE11HXYZ1E
# ---
# ➃ LXYZHEQXYZXYZQQHE11HXYZ1E
# ---
task.findPattern(text, pattern)
if __name__ == "__main__": main()Output
Pattern found at index 1
Pattern found at index 7
Pattern found at index 10
Pattern found at index 20# Ruby program for
# Z algorithm for pattern matching
class Matching
def calculateZValue(str, n, z)
left = 0
right = 0
k = 0
i = 1
while (i < n)
if (i > right)
left = right = i
while (right < n &&
str[right - left] == str[right])
right += 1
end
z[i] = right - left
right -= 1
else
k = i - left
if (z[k] < right - i + 1)
z[i] = z[k]
else
left = i
while (right < n &&
str[right - left] == str[right])
right += 1
end
z[i] = right - left
right -= 1
end
end
i += 1
end
end
def findPattern(text, pattern)
# Get the length of given text
n = text.length
# Get the length of given pattern
m = pattern.length
# Combine search pattern and given text
data = pattern + text
k = data.length
z = Array.new(k) {0}
self.calculateZValue(data, k, z)
i = 0
while (i < k)
if (z[i] == m)
print("Pattern found at index ", (i - m), "\n")
end
i += 1
end
end
end
def main()
task = Matching.new()
# Given text
text = "LXYZHEQXYZXYZQQHE11HXYZ1E"
# Search pattern
pattern = "XYZ"
# Find pattern which occurs in given text
# Text = LXYZHEQXYZXYZQQHE11HXYZ1E
# Pattern = XYZ
# --------------------------------
# ➀ LXYZHEQXYZXYZQQHE11HXYZ1E
# ---
# ➁ LXYZHEQXYZXYZQQHE11HXYZ1E
# ---
# ➂ LXYZHEQXYZXYZQQHE11HXYZ1E
# ---
# ➃ LXYZHEQXYZXYZQQHE11HXYZ1E
# ---
task.findPattern(text, pattern)
end
main()Output
Pattern found at index 1
Pattern found at index 7
Pattern found at index 10
Pattern found at index 20
import scala.collection.mutable._;
// Scala program for
// Z algorithm for pattern matching
class Matching()
{
def calculateZValue(str: String, n: Int, z: Array[Int]): Unit = {
var left: Int = 0;
var right: Int = 0;
var k: Int = 0;
var i: Int = 1;
while (i < n)
{
if (i > right)
{
left = i;
right = i;
while (right < n &&
str.charAt(right - left) == str.charAt(right))
{
right += 1;
}
z(i) = right - left;
right -= 1;
}
else
{
k = i - left;
if (z(k) < right - i + 1)
{
z(i) = z(k);
}
else
{
left = i;
while (right < n &&
str.charAt(right - left) == str.charAt(right))
{
right += 1;
}
z(i) = right - left;
right -= 1;
}
}
i += 1;
}
}
def findPattern(text: String, pattern: String): Unit = {
// Get the length of given text
var n: Int = text.length();
// Get the length of given pattern
var m: Int = pattern.length();
// Combine search pattern and given text
var data: String = pattern + text;
var k: Int = data.length();
var z: Array[Int] = Array.fill[Int](k)(0);
calculateZValue(data, k, z);
var i: Int = 0;
while (i < k)
{
if (z(i) == m)
{
println("Pattern found at index " + (i - m));
}
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Matching = new Matching();
// Given text
var text: String = "LXYZHEQXYZXYZQQHE11HXYZ1E";
// Search pattern
var pattern: String = "XYZ";
// Find pattern which occurs in given text
/*
Text = LXYZHEQXYZXYZQQHE11HXYZ1E
Pattern = XYZ
--------------------------------
➀ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➁ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➂ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➃ LXYZHEQXYZXYZQQHE11HXYZ1E
---
*/
task.findPattern(text, pattern);
}
}Output
Pattern found at index 1
Pattern found at index 7
Pattern found at index 10
Pattern found at index 20import Foundation;
// Swift 4 program for
// Z algorithm for pattern matching
class Matching
{
func calculateZValue(_ str: [Character], _ n: Int, _ z: inout[Int])
{
var left: Int = 0;
var right: Int = 0;
var k: Int = 0;
var i: Int = 1;
while (i < n)
{
if (i > right)
{
left = i;
right = i;
while (right < n &&
str[right - left] == str[right])
{
right += 1;
}
z[i] = right - left;
right -= 1;
}
else
{
k = i - left;
if (z[k] < right - i + 1)
{
z[i] = z[k];
}
else
{
left = i;
while (right < n &&
str[right - left] == str[right])
{
right += 1;
}
z[i] = right - left;
right -= 1;
}
}
i += 1;
}
}
func findPattern(_ text: String, _ pattern: String)
{
// Get the length of given pattern
let m: Int = pattern.count;
// Combine search pattern and given text
let data: String = pattern + text;
let k: Int = data.count;
var z: [Int] = Array(repeating: 0, count: k);
self.calculateZValue(Array(data), k, &z);
var i: Int = 0;
while (i < k)
{
if (z[i] == m)
{
print("Pattern found at index ", (i - m));
}
i += 1;
}
}
}
func main()
{
let task: Matching = Matching();
// Given text
let text: String = "LXYZHEQXYZXYZQQHE11HXYZ1E";
// Search pattern
let pattern: String = "XYZ";
// Find pattern which occurs in given text
/*
Text = LXYZHEQXYZXYZQQHE11HXYZ1E
Pattern = XYZ
--------------------------------
➀ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➁ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➂ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➃ LXYZHEQXYZXYZQQHE11HXYZ1E
---
*/
task.findPattern(text, pattern);
}
main();Output
Pattern found at index 1
Pattern found at index 7
Pattern found at index 10
Pattern found at index 20// Kotlin program for
// Z algorithm for pattern matching
class Matching
{
fun calculateZValue(str: String, n: Int, z: Array < Int > ): Unit
{
var left: Int = 0;
var right: Int = 0;
var k: Int ;
var i: Int = 1;
while (i < n)
{
if (i > right)
{
left = i;
right = i;
while (right < n &&
str.get(right - left) == str.get(right))
{
right += 1;
}
z[i] = right - left;
right -= 1;
}
else
{
k = i - left;
if (z[k] < right - i + 1)
{
z[i] = z[k];
}
else
{
left = i;
while (right < n &&
str.get(right - left) == str.get(right))
{
right += 1;
}
z[i] = right - left;
right -= 1;
}
}
i += 1;
}
}
fun findPattern(text: String, pattern: String): Unit
{
// Get the length of given pattern
val m: Int = pattern.length;
// Combine search pattern and given text
val data: String = pattern + text;
val k: Int = data.length;
val z: Array < Int > = Array(k)
{
0
};
this.calculateZValue(data, k, z);
var i: Int = 0;
while (i < k)
{
if (z[i] == m)
{
println("Pattern found at index " + (i - m));
}
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
val task: Matching = Matching();
// Given text
val text: String = "LXYZHEQXYZXYZQQHE11HXYZ1E";
// Search pattern
val pattern: String = "XYZ";
// Find pattern which occurs in given text
/*
Text = LXYZHEQXYZXYZQQHE11HXYZ1E
Pattern = XYZ
--------------------------------
➀ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➁ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➂ LXYZHEQXYZXYZQQHE11HXYZ1E
---
➃ LXYZHEQXYZXYZQQHE11HXYZ1E
---
*/
task.findPattern(text, pattern);
}Output
Pattern found at index 1
Pattern found at index 7
Pattern found at index 10
Pattern found at index 20
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment