# 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)
{
// 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
---
*/
}
}``````

#### 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()
{
// 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
---
*/
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)
{
// 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
---
*/
}
}``````

#### Output

``````Pattern found at index 1
Pattern found at index 7
Pattern found at index 10
Pattern found at index 20``````
``````package 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
---
*/
}``````

#### 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()
{
// Given text
\$text = "LXYZHEQXYZXYZQQHE11HXYZ1E";
// Search pattern
\$pattern = "XYZ";
// Find pattern which occurs in given text
/*
Text = LXYZHEQXYZXYZQQHE11HXYZ1E
Pattern = XYZ
--------------------------------
➀  LXYZHEQXYZXYZQQHE11HXYZ1E
---
➁  LXYZHEQXYZXYZQQHE11HXYZ1E
---
➂  LXYZHEQXYZXYZQQHE11HXYZ1E
---
➃  LXYZHEQXYZXYZQQHE11HXYZ1E
---
*/
}
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()
{
// 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
---
*/
}
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() :
#  Given text
text = "LXYZHEQXYZXYZQQHE11HXYZ1E"
#  Search pattern
pattern = "XYZ"
#  Find pattern which occurs in given text
#    Text = LXYZHEQXYZXYZQQHE11HXYZ1E
#    Pattern = XYZ
#    --------------------------------
#    ➀  LXYZHEQXYZXYZQQHE11HXYZ1E
#        ---
#    ➁  LXYZHEQXYZXYZQQHE11HXYZ1E
#              ---
#    ➂  LXYZHEQXYZXYZQQHE11HXYZ1E
#                 ---
#    ➃  LXYZHEQXYZXYZQQHE11HXYZ1E
#                           ---

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()
#  Given text
text = "LXYZHEQXYZXYZQQHE11HXYZ1E"
#  Search pattern
pattern = "XYZ"
#  Find pattern which occurs in given text
#    Text = LXYZHEQXYZXYZQQHE11HXYZ1E
#    Pattern = XYZ
#    --------------------------------
#    ➀  LXYZHEQXYZXYZQQHE11HXYZ1E
#        ---
#    ➁  LXYZHEQXYZXYZQQHE11HXYZ1E
#              ---
#    ➂  LXYZHEQXYZXYZQQHE11HXYZ1E
#                 ---
#    ➃  LXYZHEQXYZXYZQQHE11HXYZ1E
#                            ---
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
---
*/
}
}``````

#### Output

``````Pattern found at index 1
Pattern found at index 7
Pattern found at index 10
Pattern found at index 20``````
``````import 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()
{
// 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
---
*/
}
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
{
// 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
---
*/
}``````

#### Output

``````Pattern found at index 1
Pattern found at index 7
Pattern found at index 10
Pattern found at index 20``````

## Comment

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.