Skip to main content

Rabin-karp algorithm for pattern searching

Here given code implementation process.

// C Program 
// Rabin-karp algorithm for pattern searching
#include <stdio.h>

//  Handles the request to find pattern in given text
void search(char text[], char pattern[], int n, int m)
{
	// Number of characters in alphabet
	int d = 256;
	//  prime modulus is 101
	int q = 101;
	// text hash 
	int t = 0;
	// pattern hash
	int p = 0;
	// hash function h
	int h = 1;
	// Loop controlling variable i and j
	int i = 0;
	int j = 0;
	// Calaculate pow(d, M-1)%q
	for (i = 0; i < m - 1; i++)
	{
		h = (h *d) % q;
	}
	// Calculate hash value
	for (i = 0; i < m; i++)
	{
		// hash of pattern
		p = (d *p + pattern[i]) % q;
		// hash of text
		t = (d *t + text[i]) % q;
	}
	// Display Given Data
	printf("\n Given text : %s", text);
	printf("\n Given pattern : %s\n", pattern);
	// Find pattern in text
	for (i = 0; i <= n - m; i++)
	{
		if (p == t)
		{
			while (j < m && text[i + j] == pattern[j])
			{
				j++;
			}
			if (j == m)
			{
				// When pattern exists print its starting index
				printf(" Pattern exists at index %d \n", i);
			}
			j = 0;
		}
		if (i < n - m)
		{
			t = (d *(t - text[i] *h) + text[i + m]) % q;
			if (t < 0)
			{
				// When t is less than zero
				// Then change t
				t = (t + q);
			}
		}
	}
}
int main()
{
	char text[] = "LXYZHEQXYZXYZQQHE11HXYZ1E";
	char pattern[] = "XYZ";
	int n = sizeof(text) / sizeof(text[0]) - 1;
	int m = sizeof(pattern) / sizeof(pattern[0]) - 1;
	search(text, pattern, n, m);
	return 0;
}

Output

 Given text : LXYZHEQXYZXYZQQHE11HXYZ1E
 Given pattern : XYZ
 Pattern exists at index 1
 Pattern exists at index 7
 Pattern exists at index 10
 Pattern exists at index 20
/*
  Java Program 
  Rabin-karp algorithm for pattern searching
*/
public class RabinKarp
{
	//  Handles the request to find pattern in given text
	public void search(String text, String pattern, int n, int m)
	{
		// Number of characters in alphabet
		int d = 256;
		//  prime modulus is 101
		int q = 101;
		// text hash 
		int t = 0;
		// pattern hash
		int p = 0;
		// hash function h
		int h = 1;
		// Loop controlling variable i and j
		int i = 0;
		int j = 0;
		// Calaculate pow(d, M-1)%q
		for (i = 0; i < m - 1; i++)
		{
			h = (h * d) % q;
		}
		// Calculate hash value
		for (i = 0; i < m; i++)
		{
			// hash of pattern
			p = (d * p + pattern.charAt(i)) % q;
			// hash of text
			t = (d * t + text.charAt(i)) % q;
		}
		// Display Given Data
		System.out.print("\n Given text : " + text);
		System.out.print("\n Given pattern : " + pattern + "\n");
		// Find pattern in text
		for (i = 0; i <= n - m; i++)
		{
			if (p == t)
			{
				while (j < m && text.charAt(i + j) == pattern.charAt(j))
				{
					j++;
				}
				if (j == m)
				{
					// When pattern exists print its starting index
					System.out.print(" Pattern exists at index " + i + " \n");
				}
				j = 0;
			}
			if (i < n - m)
			{
				t = (d * (t - text.charAt(i) * h) + text.charAt(i + m)) % q;
				if (t < 0)
				{
					// When t is less than zero
					// Then change t
					t = (t + q);
				}
			}
		}
	}
	public static void main(String[] args)
	{
		RabinKarp task = new RabinKarp();
		String text = "LXYZHEQXYZXYZQQHE11HXYZ1E";
		String pattern = "XYZ";
		int n = text.length();
		int m = pattern.length();
		// Test
		task.search(text, pattern, n, m);
	}
}

Output

 Given text : LXYZHEQXYZXYZQQHE11HXYZ1E
 Given pattern : XYZ
 Pattern exists at index 1
 Pattern exists at index 7
 Pattern exists at index 10
 Pattern exists at index 20
// Include namespace system
using System;
/*
  C# Program 
  Rabin-karp algorithm for pattern searching
*/
public class RabinKarp
{
	//  Handles the request to find pattern in given text
	public void search(String text, String pattern, int n, int m)
	{
		// Number of characters in alphabet
		int d = 256;
		//  prime modulus is 101
		int q = 101;
		// text hash
		int t = 0;
		// pattern hash
		int p = 0;
		// hash function h
		int h = 1;
		// Loop controlling variable i and j
		int i = 0;
		int j = 0;
		// Calaculate pow(d, M-1)%q
		while (i < m - 1)
		{
			h = (h * d) % q;
			i++;
		}
		i = 0;
		// Calculate hash value
		while (i < m)
		{
			// hash of pattern
			p = (d * p + pattern[i]) % q;
			// hash of text
			t = (d * t + text[i]) % q;
			i++;
		}
		// Display Given Data
		Console.Write("\n Given text : " + text);
		Console.Write("\n Given pattern : " + pattern + "\n");
		i = 0;
		// Find pattern in text
		while (i <= n - m)
		{
			if (p == t)
			{
				while (j < m && text[i + j] == pattern[j])
				{
					j++;
				}
				if (j == m)
				{
					// When pattern exists print its starting index
					Console.Write(" Pattern exists at index " + i + " \n");
				}
				j = 0;
			}
			if (i < n - m)
			{
				t = (d * (t - text[i] * h) + text[i + m]) % q;
				if (t < 0)
				{
					// When t is less than zero
					// Then change t
					t = (t + q);
				}
			}
			i++;
		}
	}
	public static void Main(String[] args)
	{
		RabinKarp task = new RabinKarp();
		String text = "LXYZHEQXYZXYZQQHE11HXYZ1E";
		String pattern = "XYZ";
		int n = text.Length;
		int m = pattern.Length;
		// Test
		task.search(text, pattern, n, m);
	}
}

Output

 Given text : LXYZHEQXYZXYZQQHE11HXYZ1E
 Given pattern : XYZ
 Pattern exists at index 1
 Pattern exists at index 7
 Pattern exists at index 10
 Pattern exists at index 20
// Include header file
#include <iostream>
#include <string>
using namespace std;
/*
  C++ Program 
  Rabin-karp algorithm for pattern searching
*/
class RabinKarp
{
	public:
		//  Handles the request to find pattern in given text
		void search(string text, string pattern, int n, int m)
		{
			// Number of characters in alphabet
			int d = 256;
			//  prime modulus is 101
			int q = 101;
			// text hash
			int t = 0;
			// pattern hash
			int p = 0;
			// hash function h
			int h = 1;
			// Loop controlling variable i and j
			int i = 0;
			int j = 0;
			// Calaculate pow(d, M-1)%q
			for (i = 0; i < m - 1; i++)
			{
				h = (h *d) % q;
			}
			// Calculate hash value
			for (i = 0; i < m; i++)
			{
				// hash of pattern
				p = (d *p + pattern[i]) % q;
				// hash of text
				t = (d *t + text[i]) % q;
			}
			// Display Given Data
			cout << "\n Given text : " << text;
			cout << "\n Given pattern : " << pattern << "\n";
			// Find pattern in text
			for (i = 0; i <= n - m; i++)
			{
				if (p == t)
				{
					while (j < m && text[i + j] == pattern[j])
					{
						j++;
					}
					if (j == m)
					{
						// When pattern exists print its starting index
						cout << " Pattern exists at index " << i << " \n";
					}
					j = 0;
				}
				if (i < n - m)
				{
					t = (d *(t - text[i] *h) + text[i + m]) % q;
					if (t < 0)
					{
						// When t is less than zero
						// Then change t
						t = (t + q);
					}
				}
			}
		}
};
int main()
{
	RabinKarp task = RabinKarp();
	string text = "LXYZHEQXYZXYZQQHE11HXYZ1E";
	string pattern = "XYZ";
	int n = text.length();
	int m = pattern.length();
	// Test
	task.search(text, pattern, n, m);
	return 0;
}

Output

 Given text : LXYZHEQXYZXYZQQHE11HXYZ1E
 Given pattern : XYZ
 Pattern exists at index 1
 Pattern exists at index 7
 Pattern exists at index 10
 Pattern exists at index 20
<?php
/*
  Php Program 
  Rabin-karp algorithm for pattern searching
*/
class RabinKarp
{
	//  Handles the request to find pattern in given text
	public	function search($text, $pattern, $n, $m)
	{
		// Number of characters in alphabet
		$d = 256;
		//  prime modulus is 101
		$q = 101;
		// text hash
		$t = 0;
		// pattern hash
		$p = 0;
		// hash function h
		$h = 1;
		// Loop controlling variable i and j
		$i = 0;
		$j = 0;
		// Calaculate pow(d, M-1)%q
		for ($i = 0; $i < $m - 1; $i++)
		{
			$h = ($h * $d) % $q;
		}
		// Calculate hash value
		for ($i = 0; $i < $m; $i++)
		{
			// hash of pattern
			$p = ($d * $p + $pattern[$i]) % $q;
			// hash of text
			$t = ($d * $t + $text[$i]) % $q;
		}
		// Display Given Data
		echo "\n Given text : ". $text;
		echo "\n Given pattern : ". $pattern ."\n";
		// Find pattern in text
		for ($i = 0; $i <= $n - $m; $i++)
		{
			if ($p == $t)
			{
				while ($j < $m && $text[$i + $j] == $pattern[$j])
				{
					$j++;
				}
				if ($j == $m)
				{
					// When pattern exists print its starting index
					echo " Pattern exists at index ". $i ." \n";
				}
				$j = 0;
			}
			if ($i < $n - $m)
			{
				$t = ($d * ($t - $text[$i] * $h) + $text[$i + $m]) % $q;
				if ($t < 0)
				{
					// When t is less than zero
					// Then change t
					$t = ($t + $q);
				}
			}
		}
	}
}

function main()
{
	$task = new RabinKarp();
	$text = "LXYZHEQXYZXYZQQHE11HXYZ1E";
	$pattern = "XYZ";
	$n = strlen($text);
	$m = strlen($pattern);
	$task->search($text, $pattern, $n, $m);
}
main();

Output

 Given text : LXYZHEQXYZXYZQQHE11HXYZ1E
 Given pattern : XYZ
 Pattern exists at index 1
 Pattern exists at index 7
 Pattern exists at index 10
 Pattern exists at index 20
/*
  Node Js Program 
  Rabin-karp algorithm for pattern searching
*/
class RabinKarp
{
	//  Handles the request to find pattern in given text
	search(text, pattern, n, m)
	{
		// Number of characters in alphabet
		var d = 256;
		//  prime modulus is 101
		var q = 101;
		// text hash
		var t = 0;
		// pattern hash
		var p = 0;
		// hash function h
		var h = 1;
		// Loop controlling variable i and j
		var i = 0;
		var j = 0;
		// Calaculate pow(d, M-1)%q
		for (i = 0; i < m - 1; i++)
		{
			h = (h * d) % q;
		}
		// Calculate hash value
		for (i = 0; i < m; i++)
		{
			// hash of pattern
			p = (d * p + pattern.charCodeAt(i)) % q;
			// hash of text
			t = (d * t + text.charCodeAt(i)) % q;
		}
		// Display Given Data
		process.stdout.write("\n Given text : " + text);
		process.stdout.write("\n Given pattern : " + pattern + "\n");
		// Find pattern in text
		for (i = 0; i <= n - m; i++)
		{
			if (p == t)
			{
				while (j < m && text.charCodeAt(i + j) == pattern.charCodeAt(j))
				{
					j++;
				}
				if (j == m)
				{
					// When pattern exists print its starting index
					process.stdout.write(" Pattern exists at index " + i + " \n");
				}
				j = 0;
			}
			if (i < n - m)
			{
				t = (d * (t - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % q;
				if (t < 0)
				{
					// When t is less than zero
					// Then change t
					t = (t + q);
				}
			}
		}
	}
}

function main()
{
	var task = new RabinKarp();
	var text = "LXYZHEQXYZXYZQQHE11HXYZ1E";
	var pattern = "XYZ";
	var n = text.length;
	var m = pattern.length;
	// Test
	task.search(text, pattern, n, m);
}
main();

Output

 Given text : LXYZHEQXYZXYZQQHE11HXYZ1E
 Given pattern : XYZ
 Pattern exists at index 1
 Pattern exists at index 7
 Pattern exists at index 10
 Pattern exists at index 20
#   Python 3 Program 
#   Rabin-karp algorithm for pattern searching

class RabinKarp :
	#   Handles the request to find pattern in given text
	def search(self, text, pattern, n, m) :
		#  Number of characters in alphabet
		d = 256
		#   prime modulus is 101
		q = 101
		#  text hash
		t = 0
		#  pattern hash
		p = 0
		#  hash function h
		h = 1
		#  Loop controlling variable i and j
		i = 0
		j = 0
		#  Calaculate pow(d, M-1)%q
		while (i < m - 1) :
			h = (h * d) % q
			i += 1
		
		i = 0
		#  Calculate hash value
		while (i < m) :
			#  hash of pattern
			p = (d * p + ord(pattern[i])) % q
			#  hash of text
			t = (d * t + ord(text[i])) % q
			i += 1
		
		#  Display Given Data
		print("\n Given text : ", text, end = "")
		print("\n Given pattern : ", pattern )
		i = 0
		#  Find pattern in text
		while (i <= n - m) :
			if (p == t) :
				while (j < m and ord(text[i + j]) == ord(pattern[j])) :
					j += 1
				
				if (j == m) :
					#  When pattern exists print its starting index
					print(" Pattern exists at index ", i ," ")
				
				j = 0
			
			if (i < n - m) :
				t = (d * (t - ord(text[i]) * h) + ord(text[i + m])) % q
				if (t < 0) :
					#  When t is less than zero
					#  Then change t
					t = (t + q)
			i += 1

def main() :
	task = RabinKarp()
	text = "LXYZHEQXYZXYZQQHE11HXYZ1E"
	pattern = "XYZ"
	n = len(text)
	m = len(pattern)
	#  Test
	task.search(text, pattern, n, m)

if __name__ == "__main__": main()

Output

 Given text :  LXYZHEQXYZXYZQQHE11HXYZ1E
 Given pattern :  XYZ
 Pattern exists at index  1
 Pattern exists at index  7
 Pattern exists at index  10
 Pattern exists at index  20
#   Ruby Program 
#   Rabin-karp algorithm for pattern searching

class RabinKarp 
	#   Handles the request to find pattern in given text
	def search(text, pattern, n, m) 
		#  Number of characters in alphabet
		d = 256
		#   prime modulus is 101
		q = 101
		#  text hash
		t = 0
		#  pattern hash
		p = 0
		#  hash function h
		h = 1
		#  Loop controlling variable i and j
		i = 0
		j = 0
		#  Calaculate pow(d, M-1)%q
		while (i < m - 1) 
			h = (h * d) % q
			i += 1
		end

		i = 0
		#  Calculate hash value
		while (i < m) 
			#  hash of pattern
			p = (d * p + pattern[i].ord) % q
			#  hash of text
			t = (d * t + text[i].ord) % q
			i += 1
		end

		#  Display Given Data
		print("\n Given text : ", text)
		print("\n Given pattern : ", pattern ,"\n")
		i = 0
		#  Find pattern in text
		while (i <= n - m) 
			if (p == t) 
				while (j < m && text[i + j] == pattern[j]) 
					j += 1
				end

				if (j == m) 
					#  When pattern exists print its starting index
					print(" Pattern exists at index ", i ," \n")
				end

				j = 0
			end

			if (i < n - m) 
				t = (d * (t - text[i].ord * h) + text[i + m].ord) % q
				if (t < 0) 
					#  When t is less than zero
					#  Then change t
					t = (t + q)
				end

			end

			i += 1
		end

	end

end

def main() 
	task = RabinKarp.new()
	text = "LXYZHEQXYZXYZQQHE11HXYZ1E"
	pattern = "XYZ"
	n = text.length
	m = pattern.length
	#  Test
	task.search(text, pattern, n, m)
end

main()

Output

 Given text : LXYZHEQXYZXYZQQHE11HXYZ1E
 Given pattern : XYZ
 Pattern exists at index 1 
 Pattern exists at index 7 
 Pattern exists at index 10 
 Pattern exists at index 20 

import scala.collection.mutable._;
/*
  Scala Program 
  Rabin-karp algorithm for pattern searching
*/
class RabinKarp
{
	//  Handles the request to find pattern in given text
	def search(text: String, pattern: String, n: Int, m: Int): Unit = {
		// Number of characters in alphabet
		var d: Int = 256;
		//  prime modulus is 101
		var q: Int = 101;
		// text hash
		var t: Int = 0;
		// pattern hash
		var p: Int = 0;
		// hash function h
		var h: Int = 1;
		// Loop controlling variable i and j
		var i: Int = 0;
		var j: Int = 0;
		// Calaculate pow(d, M-1)%q
		while (i < m - 1)
		{
			h = (h * d) % q;
			i += 1;
		}
		i = 0;
		// Calculate hash value
		while (i < m)
		{
			// hash of pattern
			p = (d * p + pattern.charAt(i)) % q;
			// hash of text
			t = (d * t + text.charAt(i)) % q;
			i += 1;
		}
		// Display Given Data
		print("\n Given text : " + text);
		print("\n Given pattern : " + pattern + "\n");
		i = 0;
		// Find pattern in text
		while (i <= n - m)
		{
			if (p == t)
			{
				while (j < m && text.charAt(i + j) == pattern.charAt(j))
				{
					j += 1;
				}
				if (j == m)
				{
					// When pattern exists print its starting index
					print(" Pattern exists at index " + i + " \n");
				}
				j = 0;
			}
			if (i < n - m)
			{
				t = (d * (t - text.charAt(i) * h) + text.charAt(i + m)) % q;
				if (t < 0)
				{
					// When t is less than zero
					// Then change t
					t = (t + q);
				}
			}
			i += 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: RabinKarp = new RabinKarp();
		var text: String = "LXYZHEQXYZXYZQQHE11HXYZ1E";
		var pattern: String = "XYZ";
		var n: Int = text.length();
		var m: Int = pattern.length();
		// Test
		task.search(text, pattern, n, m);
	}
}

Output

 Given text : LXYZHEQXYZXYZQQHE11HXYZ1E
 Given pattern : XYZ
 Pattern exists at index 1
 Pattern exists at index 7
 Pattern exists at index 10
 Pattern exists at index 20
import Foundation
/*
  Swift 4 Program 
  Rabin-karp algorithm for pattern searching
*/

class RabinKarp
{
  	func  ascii(_ ch : Character) -> Int
    {
      
      	return Int(UnicodeScalar(String(ch))!.value);
    }
	//  Handles the request to find pattern in given text
	func search(_ txt: String, _ pt: String, _ n: Int, _ m: Int)
	{
      
  		let text = Array(txt);
      	let pattern = Array(pt);
		// Number of characters in alphabet
		let d: Int = 256;
		//  prime modulus is 101
		let q: Int = 101;
		// text hash
		var t: Int = 0;
		// pattern hash
		var p: Int = 0;
		// hash function h
		var h: Int = 1;
		// Loop controlling variable i and j
		var i: Int = 0;
		var j: Int = 0;
		// Calaculate pow(d, M-1)%q
		while (i < m - 1)
		{
			h = (h * d) % q;
			i += 1;
		}
		i = 0;
		// Calculate hash value
		while (i < m)
		{
			// hash of pattern
			p = (d * p + ascii(pattern[i])) % q;
			// hash of text
			t = (d * t + ascii(text[i])) % q;
			i += 1;
		}
		// Display Given Data
		print("\n Given text : ", txt, terminator: "");
		print("\n Given pattern : ", pt );
		i = 0;
		// Find pattern in text
		while (i <= n - m)
		{
			if (p == t)
			{
				while (j < m && text[i + j] == pattern[j])
				{
					j += 1;
				}
				if (j == m)
				{
					// When pattern exists print its starting index
					print(" Pattern exists at index ", i ," ");
				}
				j = 0;
			}
			if (i < n - m)
			{
				t = (d * (t - ascii(text[i]) * h) + ascii(text[i + m])) % q;
				if (t < 0)
				{
					// When t is less than zero
					// Then change t
					t = (t + q);
				}
			}
			i += 1;
		}
	}
}
func main()
{
	let task: RabinKarp = RabinKarp();
	let text: String = "LXYZHEQXYZXYZQQHE11HXYZ1E";
	let pattern: String = "XYZ";
	let n: Int = text.count;
	let m: Int = pattern.count;
	// Test
	task.search(text, pattern, n, m);
}
main();

Output

 Given text :  LXYZHEQXYZXYZQQHE11HXYZ1E
 Given pattern :  XYZ
 Pattern exists at index  1
 Pattern exists at index  7
 Pattern exists at index  10
 Pattern exists at index  20
/*
  Kotlin Program 
  Rabin-karp algorithm for pattern searching
*/
class RabinKarp
{
	//  Handles the request to find pattern in given text
	fun search(text: String, pattern: String, n: Int, m: Int): Unit
	{
		// Number of characters in alphabet
		var d: Int = 256;
		//  prime modulus is 101
		var q: Int = 101;
		// text hash
		var t: Int = 0;
		// pattern hash
		var p: Int = 0;
		// hash function h
		var h: Int = 1;
		// Loop controlling variable i and j
		var i: Int = 0;
		var j: Int = 0;
		// Calaculate pow(d, M-1)%q
		while (i < m - 1)
		{
			h = (h * d) % q;
			i += 1;
		}
		i = 0;
		// Calculate hash value
		while (i < m)
		{
			// hash of pattern
			p = (d * p + pattern.get(i).toInt()) % q;
			// hash of text
			t = (d * t + text.get(i).toInt()) % q;
			i += 1;
		}
		// Display Given Data
		print("\n Given text : " + text);
		print("\n Given pattern : " + pattern + "\n");
		i = 0;
		// Find pattern in text
		while (i <= n - m)
		{
			if (p == t)
			{
				while (j < m && text.get(i + j) == pattern.get(j))
				{
					j += 1;
				}
				if (j == m)
				{
					// When pattern exists print its starting index
					print(" Pattern exists at index " + i + " \n");
				}
				j = 0;
			}
			if (i < n - m)
			{
				t = (d * (t - text.get(i).toInt() * h) + text.get(i + m).toInt()) % q;
				if (t < 0)
				{
					// When t is less than zero
					// Then change t
					t = (t + q);
				}
			}
			i += 1;
		}
	}
}
fun main(args: Array < String > ): Unit
{
	var task: RabinKarp = RabinKarp();
	var text: String = "LXYZHEQXYZXYZQQHE11HXYZ1E";
	var pattern: String = "XYZ";
	var n: Int = text.length;
	var m: Int = pattern.length;
	// Test
	task.search(text, pattern, n, m);
}

Output

 Given text : LXYZHEQXYZXYZQQHE11HXYZ1E
 Given pattern : XYZ
 Pattern exists at index 1
 Pattern exists at index 7
 Pattern exists at index 10
 Pattern exists 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