« Previous Next »

KMP algorithm for pattern searching

Here given code implementation process.

// C program 
// KMP algorithm for pattern searching
#include <stdio.h>
#include <string.h>

// Find prefix and suffix length 
void prefix_suffix(const char *pattern, int m, int position[])
{
	// First position will be zero
	position[0] = 0;
	int length = 0;
	int i = 1;
	while (i < m)
	{
		if (pattern[i] == pattern[length])
		{
			position[i] = length + 1;
			length = position[i];
			i++;
		}
		else
		{
			if (length != 0)
			{
				length = position[length - 1];
			}
			else
			{
				position[i] = 0;
				i++;
			}
		}
	}
}
// Find all location of pattern in given text
void kmp_algorithm(const char *text , const char *pattern)
{
	// Get the length of pattern
	int m = strlen(pattern);
	// Get the length of given text
	int n = strlen(text);
	// Display given text and pattern
	printf("\n Test    : [%s]", text);
	printf("\n Pattern : [%s]", pattern);
	printf("\n Pattern exist in following index : \n");
	// result indicator
	int status = 0;
	if (m > 0 && n > 0)
	{
		// Loop controlling variables i and j
		int i = 0;
		int j = 0;
		// Use to collect position of longest suffix and prefix
		int position[m];
		// Find position of longest prefix suffix 
		prefix_suffix(pattern, m, position);
		// Execute loop through by text length
		while (i < n)
		{
			if (pattern[j] == text[i])
			{
				j++;
				i++;
			}
			if (j == m)
			{
				// When get a new pattern
				printf(" Pattern at index %d\n", i - j);
				j = position[j - 1];
				status = 1;
			}
			else if (i < n && pattern[j] != text[i])
			{
				if (j != 0)
				{
					j = position[j - 1];
				}
				else
				{
					i = i + 1;
				}
			}
		}
	}
	if (status == 0)
	{
		printf("\n None \n");
	}
}
int main(int argc, char
	const *argv[])
{
	// Given text
	const char *text = "This is historic distance division sector for tourist";
	// Given pattern
	const char *pattern = "is";
	kmp_algorithm(text, pattern);
	return 0;
}

Output

 Test    : [This is historic distance division sector for tourist]
 Pattern : [is]
 Pattern exist in following index :
 Pattern at index 2
 Pattern at index 5
 Pattern at index 9
 Pattern at index 18
 Pattern at index 29
 Pattern at index 50

/*
  Java program
  KMP algorithm for pattern searching
*/
public class Searching
{
    // Find prefix and suffix length 
    public void prefixSuffix(String pattern, int m, int[] position)
    {
        // First position will be zero
        position[0] = 0;
        int length = 0;
        int i = 1;
        while (i < m)
        {
            if (pattern.charAt(i) == pattern.charAt(length))
            {
                position[i] = length + 1;
                length = position[i];
                i++;
            }
            else
            {
                if (length != 0)
                {
                    length = position[length - 1];
                }
                else
                {
                    position[i] = 0;
                    i++;
                }
            }
        }
    }
    // Find all location of pattern in given text
    public void kmpAlgorithm(String text, String pattern)
    {
        // Get the length of pattern
        int m = pattern.length();
        // Get the length of given text
        int n = text.length();
        // Display given text and pattern
        System.out.print("\n Test : [" + text + "]");
        System.out.print("\n Pattern : [" + pattern + "]");
        System.out.print("\n Pattern exist in following index : \n");
        // result indicator
        boolean status = false;
        if (m > 0 && n > 0)
        {
            // Loop controlling variables i and j
            int i = 0;
            int j = 0;
            // Use to collect position of longest suffix and prefix
            int[] position = new int[m];
            // Find position of longest prefix suffix 
            prefixSuffix(pattern, m, position);
            // Execute loop through by text length
            while (i < n)
            {
                if (pattern.charAt(j) == text.charAt(i))
                {
                    j++;
                    i++;
                }
                if (j == m)
                {
                    // When get a new pattern
                    System.out.print(" Pattern at index " + (i - j) + "\n");
                    j = position[j - 1];
                    status = true;
                }
                else if (i < n && pattern.charAt(j) != text.charAt(i))
                {
                    if (j != 0)
                    {
                        j = position[j - 1];
                    }
                    else
                    {
                        i = i + 1;
                    }
                }
            }
        }
        if (status == false)
        {
            System.out.print("\n None \n");
        }
    }
    public static void main(String[] args)
    {
        Searching task = new Searching();
        // Given text
        String text = "This is historic distance division sector for tourist";
        // Given pattern
        String pattern = "is";
        task.kmpAlgorithm(text, pattern);
    }
}

Output

 Test : [This is historic distance division sector for tourist]
 Pattern : [is]
 Pattern exist in following index :
 Pattern at index 2
 Pattern at index 5
 Pattern at index 9
 Pattern at index 18
 Pattern at index 29
 Pattern at index 50

// Include header file
#include <iostream>
#include <string>
using namespace std;

/*
  C++ program
  KMP algorithm for pattern searching
*/
class Searching
{
	public:
		// Find prefix and suffix length
		void prefixSuffix(string pattern, int m, int position[])
		{
			// First position will be zero
			position[0] = 0;
			int length = 0;
			int i = 1;
			while (i < m)
			{
				if (pattern[i] == pattern[length])
				{
					position[i] = length + 1;
					length = position[i];
					i++;
				}
				else
				{
					if (length != 0)
					{
						length = position[length - 1];
					}
					else
					{
						position[i] = 0;
						i++;
					}
				}
			}
		}
	// Find all location of pattern in given text
	void kmpAlgorithm(string text, string pattern)
	{
		// Get the length of pattern
		int m = pattern.length();
		// Get the length of given text
		int n = text.length();
		// Display given text and pattern
		cout << "\n Test : [" << text << "]";
		cout << "\n Pattern : [" << pattern << "]";
		cout << "\n Pattern exist in following index : \n";
		// result indicator
		bool status = false;
		if (m > 0 && n > 0)
		{
			// Loop controlling variables i and j
			int i = 0;
			int j = 0;
			// Use to collect position of longest suffix and prefix
			int position[m];
			// Find position of longest prefix suffix
			this->prefixSuffix(pattern, m, position);
			// Execute loop through by text length
			while (i < n)
			{
				if (pattern[j] == text[i])
				{
					j++;
					i++;
				}
				if (j == m)
				{
					// When get a new pattern
					cout << " Pattern at index " << (i - j) << "\n";
					j = position[j - 1];
					status = true;
				}
				else if (i < n && pattern[j] != text[i])
				{
					if (j != 0)
					{
						j = position[j - 1];
					}
					else
					{
						i = i + 1;
					}
				}
			}
		}
		if (status == false)
		{
			cout << "\n None \n";
		}
	}
};
int main()
{
	Searching task = Searching();
	// Given text
	string text = "This is historic distance division sector for tourist";
	// Given pattern
	string pattern = "is";
	task.kmpAlgorithm(text, pattern);
	return 0;
}

Output

 Test : [This is historic distance division sector for tourist]
 Pattern : [is]
 Pattern exist in following index :
 Pattern at index 2
 Pattern at index 5
 Pattern at index 9
 Pattern at index 18
 Pattern at index 29
 Pattern at index 50

// Include namespace system
using System;
/*
  C# program
  KMP algorithm for pattern searching
*/
public class Searching
{
	// Find prefix and suffix length
	public void prefixSuffix(String pattern, int m, int[] position)
	{
		// First position will be zero
		position[0] = 0;
		int length = 0;
		int i = 1;
		while (i < m)
		{
			if (pattern[i] == pattern[length])
			{
				position[i] = length + 1;
				length = position[i];
				i++;
			}
			else
			{
				if (length != 0)
				{
					length = position[length - 1];
				}
				else
				{
					position[i] = 0;
					i++;
				}
			}
		}
	}
	// Find all location of pattern in given text
	public void kmpAlgorithm(String text, String pattern)
	{
		// Get the length of pattern
		int m = pattern.Length;
		// Get the length of given text
		int n = text.Length;
		// Display given text and pattern
		Console.Write("\n Test : [" + text + "]");
		Console.Write("\n Pattern : [" + pattern + "]");
		Console.Write("\n Pattern exist in following index : \n");
		// result indicator
		Boolean status = false;
		if (m > 0 && n > 0)
		{
			// Loop controlling variables i and j
			int i = 0;
			int j = 0;
			// Use to collect position of longest suffix and prefix
			int[] position = new int[m];
			// Find position of longest prefix suffix
			prefixSuffix(pattern, m, position);
			// Execute loop through by text length
			while (i < n)
			{
				if (pattern[j] == text[i])
				{
					j++;
					i++;
				}
				if (j == m)
				{
					// When get a new pattern
					Console.Write(" Pattern at index " + (i - j) + "\n");
					j = position[j - 1];
					status = true;
				}
				else if (i < n && pattern[j] != text[i])
				{
					if (j != 0)
					{
						j = position[j - 1];
					}
					else
					{
						i = i + 1;
					}
				}
			}
		}
		if (status == false)
		{
			Console.Write("\n None \n");
		}
	}
	public static void Main(String[] args)
	{
		Searching task = new Searching();
		// Given text
		String text = "This is historic distance division sector for tourist";
		// Given pattern
		String pattern = "is";
		task.kmpAlgorithm(text, pattern);
	}
}

Output

 Test : [This is historic distance division sector for tourist]
 Pattern : [is]
 Pattern exist in following index :
 Pattern at index 2
 Pattern at index 5
 Pattern at index 9
 Pattern at index 18
 Pattern at index 29
 Pattern at index 50

<?php
/*
  Php program
  KMP algorithm for pattern searching
*/
class Searching
{
	// Find prefix and suffix length
	public	function prefixSuffix($pattern, $m, & $position)
	{
		// First position will be zero
		$position[0] = 0;
		$length = 0;
		$i = 1;
		while ($i < $m)
		{
			if ($pattern[$i] == $pattern[$length])
			{
				$position[$i] = $length + 1;
				$length = $position[$i];
				$i++;
			}
			else
			{
				if ($length != 0)
				{
					$length = $position[$length - 1];
				}
				else
				{
					$position[$i] = 0;
					$i++;
				}
			}
		}
	}
	// Find all location of pattern in given text
	public	function kmpAlgorithm($text, $pattern)
	{
		// Get the length of pattern
		$m = strlen($pattern);
		// Get the length of given text
		$n = strlen($text);
		// Display given text and pattern
		echo "\n Test : [". $text ."]";
		echo "\n Pattern : [". $pattern ."]";
		echo "\n Pattern exist in following index : \n";
		// result indicator
		$status = false;
		if ($m > 0 && $n > 0)
		{
			// Loop controlling variables i and j
			$i = 0;
			$j = 0;
			// Use to collect position of longest suffix and prefix
			$position = array_fill(0, $m, 0);
			// Find position of longest prefix suffix
			$this->prefixSuffix($pattern, $m, $position);
			// Execute loop through by text length
			while ($i < $n)
			{
				if ($pattern[$j] == $text[$i])
				{
					$j++;
					$i++;
				}
				if ($j == $m)
				{
					// When get a new pattern
					echo " Pattern at index ". ($i - $j) ."\n";
					$j = $position[$j - 1];
					$status = true;
				}
				else if ($i < $n && $pattern[$j] != $text[$i])
				{
					if ($j != 0)
					{
						$j = $position[$j - 1];
					}
					else
					{
						$i = $i + 1;
					}
				}
			}
		}
		if ($status == false)
		{
			echo "\n None \n";
		}
	}
}

function main()
{
	$task = new Searching();
	// Given text
	$text = "This is historic distance division sector for tourist";
	// Given pattern
	$pattern = "is";
	$task->kmpAlgorithm($text, $pattern);
}
main();

Output

 Test : [This is historic distance division sector for tourist]
 Pattern : [is]
 Pattern exist in following index :
 Pattern at index 2
 Pattern at index 5
 Pattern at index 9
 Pattern at index 18
 Pattern at index 29
 Pattern at index 50

/*
  Node Js program
  KMP algorithm for pattern searching
*/
class Searching
{
	// Find prefix and suffix length
	prefixSuffix(pattern, m, position)
	{
		// First position will be zero
		position[0] = 0;
		var length = 0;
		var i = 1;
		while (i < m)
		{
			if (pattern.charAt(i) == pattern.charAt(length))
			{
				position[i] = length + 1;
				length = position[i];
				i++;
			}
			else
			{
				if (length != 0)
				{
					length = position[length - 1];
				}
				else
				{
					position[i] = 0;
					i++;
				}
			}
		}
	}
	// Find all location of pattern in given text
	kmpAlgorithm(text, pattern)
	{
		// Get the length of pattern
		var m = pattern.length;
		// Get the length of given text
		var n = text.length;
		// Display given text and pattern
		process.stdout.write("\n Test : [" + text + "]");
		process.stdout.write("\n Pattern : [" + pattern + "]");
		process.stdout.write("\n Pattern exist in following index : \n");
		// result indicator
		var status = false;
		if (m > 0 && n > 0)
		{
			// Loop controlling variables i and j
			var i = 0;
			var j = 0;
			// Use to collect position of longest suffix and prefix
			var position = Array(m).fill(0);
			// Find position of longest prefix suffix
			this.prefixSuffix(pattern, m, position);
			// Execute loop through by text length
			while (i < n)
			{
				if (pattern.charAt(j) == text.charAt(i))
				{
					j++;
					i++;
				}
				if (j == m)
				{
					// When get a new pattern
					process.stdout.write(" Pattern at index " + (i - j) + "\n");
					j = position[j - 1];
					status = true;
				}
				else if (i < n && pattern.charAt(j) != text.charAt(i))
				{
					if (j != 0)
					{
						j = position[j - 1];
					}
					else
					{
						i = i + 1;
					}
				}
			}
		}
		if (status == false)
		{
			process.stdout.write("\n None \n");
		}
	}
}

function main()
{
	var task = new Searching();
	// Given text
	var text = "This is historic distance division sector for tourist";
	// Given pattern
	var pattern = "is";
	task.kmpAlgorithm(text, pattern);
}
main();

Output

 Test : [This is historic distance division sector for tourist]
 Pattern : [is]
 Pattern exist in following index :
 Pattern at index 2
 Pattern at index 5
 Pattern at index 9
 Pattern at index 18
 Pattern at index 29
 Pattern at index 50

#   Python 3 program
#   KMP algorithm for pattern searching

class Searching :
	#  Find prefix and suffix length 
	def prefixSuffix(self, pattern, m, position) :
		#  First position will be zero
		position[0] = 0
		length = 0
		i = 1
		while (i < m) :
			if (pattern[i] == pattern[length]) :
				position[i] = length + 1
				length = position[i]
				i += 1
			else :
				if (length != 0) :
					length = position[length - 1]
				else :
					position[i] = 0
					i += 1
				
			
		
	
	#  Find all location of pattern in given text
	def kmpAlgorithm(self, text, pattern) :
		#  Get the length of pattern
		m = len(pattern)
		#  Get the length of given text
		n = len(text)
		#  Display given text and pattern
		print("\n Test : [", text ,"]", end = "")
		print("\n Pattern : [", pattern ,"]", end = "")
		print("\n Pattern exist in following index : ")
		#  result indicator
		status = False
		if (m > 0 and n > 0) :
			#  Loop controlling variables i and j
			i = 0
			j = 0
			#  Use to collect position of longest suffix and prefix
			position = [0] * (m)
			#  Find position of longest prefix suffix 
			self.prefixSuffix(pattern, m, position)
			#  Execute loop through by text length
			while (i < n) :
				if (pattern[j] == text[i]) :
					j += 1
					i += 1
				
				if (j == m) :
					#  When get a new pattern
					print(" Pattern at index ", (i - j))
					j = position[j - 1]
					status = True
				
				elif(i < n and pattern[j] != text[i]) :
					if (j != 0) :
						j = position[j - 1]
					else :
						i = i + 1
					
				
			
		
		if (status == False) :
			print(ord("\n None \n"), end = "")
		
	

def main() :
	task = Searching()
	#  Given text
	text = "This is historic distance division sector for tourist"
	#  Given pattern
	pattern = "is"
	task.kmpAlgorithm(text, pattern)

if __name__ == "__main__": main()

Output

 Test : [ This is historic distance division sector for tourist ]
 Pattern : [ is ]
 Pattern exist in following index :
 Pattern at index  2
 Pattern at index  5
 Pattern at index  9
 Pattern at index  18
 Pattern at index  29
 Pattern at index  50

#   Ruby program
#   KMP algorithm for pattern searching

class Searching 
	#  Find prefix and suffix length 
	def prefixSuffix(pattern, m, position) 
		#  First position will be zero
		position[0] = 0
		length = 0
		i = 1
		while (i < m) 
			if (pattern[i] == pattern[length]) 
				position[i] = length + 1
				length = position[i]
				i += 1
			else 
				if (length != 0) 
					length = position[length - 1]
				else 
					position[i] = 0
					i += 1
				end

			end

		end

	end

	#  Find all location of pattern in given text
	def kmpAlgorithm(text, pattern) 
		#  Get the length of pattern
		m = pattern.length
		#  Get the length of given text
		n = text.length
		#  Display given text and pattern
		print("\n Test : [", text ,"]")
		print("\n Pattern : [", pattern ,"]")
		print("\n Pattern exist in following index : \n")
		#  result indicator
		status = false
		if (m > 0 && n > 0) 
			#  Loop controlling variables i and j
			i = 0
			j = 0
			#  Use to collect position of longest suffix and prefix
			position = Array.new(m) {0}
			#  Find position of longest prefix suffix 
			self.prefixSuffix(pattern, m, position)
			#  Execute loop through by text length
			while (i < n) 
				if (pattern[j] == text[i]) 
					j += 1
					i += 1
				end

				if (j == m) 
					#  When get a new pattern
					print(" Pattern at index ", (i - j) ,"\n")
					j = position[j - 1]
					status = true
				elsif(i < n && pattern[j] != text[i]) 
					if (j != 0) 
						j = position[j - 1]
					else 
						i = i + 1
					end

				end

			end

		end

		if (status == false) 
			print("\n None \n")
		end

	end

end

def main() 
	task = Searching.new()
	#  Given text
	text = "This is historic distance division sector for tourist"
	#  Given pattern
	pattern = "is"
	task.kmpAlgorithm(text, pattern)
end

main()

Output

 Test : [This is historic distance division sector for tourist]
 Pattern : [is]
 Pattern exist in following index : 
 Pattern at index 2
 Pattern at index 5
 Pattern at index 9
 Pattern at index 18
 Pattern at index 29
 Pattern at index 50

import scala.collection.mutable._;
/*
  Scala program
  KMP algorithm for pattern searching
*/
class Searching
{
	// Find prefix and suffix length
	def prefixSuffix(pattern: String, m: Int, position: Array[Int]): Unit = {
		// First position will be zero
		position(0) = 0;
		var length: Int = 0;
		var i: Int = 1;
		while (i < m)
		{
			if (pattern.charAt(i) == pattern.charAt(length))
			{
				position(i) = length + 1;
				length = position(i);
				i += 1;
			}
			else
			{
				if (length != 0)
				{
					length = position(length - 1);
				}
				else
				{
					position(i) = 0;
					i += 1;
				}
			}
		}
	}
	// Find all location of pattern in given text
	def kmpAlgorithm(text: String, pattern: String): Unit = {
		// Get the length of pattern
		var m: Int = pattern.length();
		// Get the length of given text
		var n: Int = text.length();
		// Display given text and pattern
		print("\n Test : [" + text + "]");
		print("\n Pattern : [" + pattern + "]");
		print("\n Pattern exist in following index : \n");
		// result indicator
		var status: Boolean = false;
		if (m > 0 && n > 0)
		{
			// Loop controlling variables i and j
			var i: Int = 0;
			var j: Int = 0;
			// Use to collect position of longest suffix and prefix
			var position: Array[Int] = Array.fill[Int](m)(0);
			// Find position of longest prefix suffix
			this.prefixSuffix(pattern, m, position);
			// Execute loop through by text length
			while (i < n)
			{
				if (pattern.charAt(j) == text.charAt(i))
				{
					j += 1;
					i += 1;
				}
				if (j == m)
				{
					// When get a new pattern
					print(" Pattern at index " + (i - j) + "\n");
					j = position(j - 1);
					status = true;
				}
				else if (i < n && pattern.charAt(j) != text.charAt(i))
				{
					if (j != 0)
					{
						j = position(j - 1);
					}
					else
					{
						i = i + 1;
					}
				}
			}
		}
		if (status == false)
		{
			print("\n None \n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Searching = new Searching();
		// Given text
		var text: String = "This is historic distance division sector for tourist";
		// Given pattern
		var pattern: String = "is";
		task.kmpAlgorithm(text, pattern);
	}
}

Output

 Test : [This is historic distance division sector for tourist]
 Pattern : [is]
 Pattern exist in following index :
 Pattern at index 2
 Pattern at index 5
 Pattern at index 9
 Pattern at index 18
 Pattern at index 29
 Pattern at index 50

/*
  Swift 4 program
  KMP algorithm for pattern searching
*/
class Searching
{
	// Find prefix and suffix length
	func prefixSuffix(_ pattern: [Character], _ m: Int, _ position: inout[Int])
	{
		// First position will be zero
		position[0] = 0;
		var length: Int = 0;
		var i: Int = 1;
		while (i < m)
		{
			if (pattern[i] == pattern[length])
			{
				position[i] = length + 1;
				length = position[i];
				i += 1;
			}
			else
			{
				if (length  != 0)
				{
					length = position[length - 1];
				}
				else
				{
					position[i] = 0;
					i += 1;
				}
			}
		}
	}
	// Find all location of pattern in given text
	func kmpAlgorithm(_ t: String, _ p: String)
	{	
      	// Convert into character array
      	let pattern = Array(p);
      	let text    = Array(t);
		// Get the length of pattern
		let m: Int = pattern.count;
		// Get the length of given text
		let n: Int = text.count;
		// Display given text and pattern
		print("\n Test : [", t ,"]", terminator: "");
		print("\n Pattern : [", p ,"]", terminator: "");
		print("\n Pattern exist in following index : ");
		// result indicator
		var status: Bool = false;
		if (m > 0 && n > 0)
		{
			// Loop controlling variables i and j
			var i: Int = 0;
			var j: Int = 0;
			// Use to collect position of longest suffix and prefix
			var position: [Int] = Array(repeating: 0, count: m);
			// Find position of longest prefix suffix
			self.prefixSuffix(pattern, m, &position);
			// Execute loop through by text length
			while (i < n)
			{
				if (pattern[j] == text[i])
				{
					j += 1;
					i += 1;
				}
				if (j == m)
				{
					// When get a new pattern
					print(" Pattern at index ", (i - j) );
					j = position[j - 1];
					status = true;
				}
				else if (i < n && pattern[j]  != text[i])
				{
					if (j  != 0)
					{
						j = position[j - 1];
					}
					else
					{
						i = i + 1;
					}
				}
			}
		}
		if (status == false)
		{
			print("\n None ");
		}
	}
}
func main()
{
	let task: Searching = Searching();
	// Given text
	let text: String = "This is historic distance division sector for tourist";
	// Given pattern
	let pattern: String = "is";
	task.kmpAlgorithm(text, pattern);
}
main();

Output

 Test : [ This is historic distance division sector for tourist ]
 Pattern : [ is ]
 Pattern exist in following index :
 Pattern at index  2
 Pattern at index  5
 Pattern at index  9
 Pattern at index  18
 Pattern at index  29
 Pattern at index  50

/*
  Kotlin program
  KMP algorithm for pattern searching
*/
class Searching
{
	// Find prefix and suffix length
	fun prefixSuffix(pattern: String, m: Int, position: Array < Int > ): Unit
	{
		// First position will be zero
		position[0] = 0;
		var length: Int = 0;
		var i: Int = 1;
		while (i < m)
		{
			if (pattern.get(i) == pattern.get(length))
			{
				position[i] = length + 1;
				length = position[i];
				i += 1;
			}
			else
			{
				if (length != 0)
				{
					length = position[length - 1];
				}
				else
				{
					position[i] = 0;
					i += 1;
				}
			}
		}
	}
	// Find all location of pattern in given text
	fun kmpAlgorithm(text: String, pattern: String): Unit
	{
		// Get the length of pattern
		var m: Int = pattern.length;
		// Get the length of given text
		var n: Int = text.length;
		// Display given text and pattern
		print("\n Test : [" + text + "]");
		print("\n Pattern : [" + pattern + "]");
		print("\n Pattern exist in following index : \n");
		// result indicator
		var status: Boolean = false;
		if (m > 0 && n > 0)
		{
			// Loop controlling variables i and j
			var i: Int = 0;
			var j: Int = 0;
			// Use to collect position of longest suffix and prefix
			var position: Array < Int > = Array(m)
			{
				0
			};
			// Find position of longest prefix suffix
			this.prefixSuffix(pattern, m, position);
			// Execute loop through by text length
			while (i < n)
			{
				if (pattern.get(j) == text.get(i))
				{
					j += 1;
					i += 1;
				}
				if (j == m)
				{
					// When get a new pattern
					print(" Pattern at index " + (i - j) + "\n");
					j = position[j - 1];
					status = true;
				}
				else if (i < n && pattern.get(j) != text.get(i))
				{
					if (j != 0)
					{
						j = position[j - 1];
					}
					else
					{
						i = i + 1;
					}
				}
			}
		}
		if (status == false)
		{
			print("\n None \n");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	var task: Searching = Searching();
	// Given text
	var text: String = "This is historic distance division sector for tourist";
	// Given pattern
	var pattern: String = "is";
	task.kmpAlgorithm(text, pattern);
}

Output

 Test : [This is historic distance division sector for tourist]
 Pattern : [is]
 Pattern exist in following index :
 Pattern at index 2
 Pattern at index 5
 Pattern at index 9
 Pattern at index 18
 Pattern at index 29
 Pattern at index 50

« Previous Next »

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.