This is a Java Program to Implement Knuth Morris Pratt Algorithm. The Knuth–Morris–Pratt string searching algorithm (or KMP algorithm) searches for occurrences of a “word” W within a main “text string” S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.
Here is the source code of the Java Program to Implement Knuth Morris Pratt Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
/**
** Java Program to implement Knuth Morris Pratt Algorithm
**/
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
/** Class KnuthMorrisPratt **/
public class KnuthMorrisPratt
{
/** Failure array **/
private int[] failure;
/** Constructor **/
public KnuthMorrisPratt(String text, String pat)
{
/** pre construct failure array for a pattern **/
failure = new int[pat.length()];
fail(pat);
/** find match **/
int pos = posMatch(text, pat);
if (pos == -1)
System.out.println("\nNo match found");
else
System.out.println("\nMatch found at index "+ pos);
}
/** Failure function for a pattern **/
private void fail(String pat)
{
int n = pat.length();
failure[0] = -1;
for (int j = 1; j < n; j++)
{
int i = failure[j - 1];
while ((pat.charAt(j) != pat.charAt(i + 1)) && i >= 0)
i = failure[i];
if (pat.charAt(j) == pat.charAt(i + 1))
failure[j] = i + 1;
else
failure[j] = -1;
}
}
/** Function to find match for a pattern **/
private int posMatch(String text, String pat)
{
int i = 0, j = 0;
int lens = text.length();
int lenp = pat.length();
while (i < lens && j < lenp)
{
if (text.charAt(i) == pat.charAt(j))
{
i++;
j++;
}
else if (j == 0)
i++;
else
j = failure[j - 1] + 1;
}
return ((j == lenp) ? (i - lenp) : -1);
}
/** Main Function **/
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Knuth Morris Pratt Test\n");
System.out.println("\nEnter Text\n");
String text = br.readLine();
System.out.println("\nEnter Pattern\n");
String pattern = br.readLine();
KnuthMorrisPratt kmp = new KnuthMorrisPratt(text, pattern);
}
}
Knuth Morris Pratt Test
Enter Text
abcdefghijklmnopqrstuvwxyz
Enter Pattern
defghij
Match found at index 3
Sanfoundry Global Education & Learning Series – 1000 Java Programs.
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.
Next Steps:
- Get Free Certificate of Merit in Java Programming
- Participate in Java Programming Certification Contest
- Become a Top Ranker in Java Programming
- Take Java Programming Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Related Posts:
- Practice Information Technology MCQs
- Buy Programming Books
- Apply for Information Technology Internship
- Practice Programming MCQs
- Apply for Java Internship