Skip to main content

KMP algorithm for pattern searching

The Knuth-Morris-Pratt (KMP) algorithm is a pattern searching algorithm that efficiently searches for occurrences of a pattern string in a text string. The KMP algorithm is based on a pre-processing step that constructs a prefix array, also known as the failure function or partial match table, which is used to avoid unnecessary comparisons during the search process.

The prefix array is computed in linear time and space complexity, and it stores the length of the longest proper prefix of the pattern string that is also a suffix of each prefix of the pattern string. This information is then used to determine the next position to compare in the text string, instead of restarting the search from the beginning of the pattern string each time there is a mismatch.

The KMP algorithm has a time complexity of O(m + n), where m is the length of the pattern string and n is the length of the text string. This makes it more efficient than naive string matching algorithms, such as the brute-force method, which has a worst-case time complexity of O(m * n).

Sure, here are the detailed steps for the KMP algorithm:

  1. Pre-process the pattern string to compute the prefix array.
    • Set the prefix array pi to be an array of length m (the length of the pattern string).
    • Set the first element of pi, pi[0], to 0.
    • Initialize two variables, i and j, to 0.
    • While i is less than m:
      • If the character at position i of the pattern string matches the character at position j of the pattern string, set pi[i] to j+1, increment both i and j.
      • If the character at position i of the pattern string does not match the character at position j of the pattern string and j is not 0, set j to pi[j-1] and try again.
      • If the character at position i of the pattern string does not match the character at position j of the pattern string and j is 0, set pi[i] to 0, increment i, and try again.
  2. Initialize two pointers, i and j, to the beginning of the text string and the pattern string, respectively.
  3. Compare the characters at positions i and j in the text and pattern strings.
  4. If the characters match, increment both pointers (i and j).
  5. If there is a mismatch and j is not at the beginning of the pattern string, update j to the value stored in the prefix array at position j-1, and compare again.
  6. If there is a mismatch and j is at the beginning of the pattern string, increment i and repeat from step 3 until the end of the text string is reached, or a match is found.

When a match is found, the starting position of the match in the text string is i - m, where m is the length of the pattern string. If no match is found, the algorithm returns -1 or an empty result, depending on the implementation.

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
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