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