Z algorithm for pattern matching

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


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







© 2021, kalkicode.com, All rights reserved