Skip to main content

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 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 
	                            ---
	*/
	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 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()
{
	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
Last updated on by Kalkicode




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.

New Comment