Java Program to Implement Knuth Morris Pratt Algorithm

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.

  1. /**
  2.  ** Java Program to implement Knuth Morris Pratt Algorithm
  3.  **/
  4.  
  5. import java.io.BufferedReader;
  6. import java.io.InputStreamReader;
  7. import java.io.IOException;
  8.  
  9. /** Class KnuthMorrisPratt **/
  10. public class KnuthMorrisPratt
  11. {
  12.     /** Failure array **/
  13.     private int[] failure;
  14.     /** Constructor **/
  15.     public KnuthMorrisPratt(String text, String pat)
  16.     {
  17.         /** pre construct failure array for a pattern **/
  18.         failure = new int[pat.length()];
  19.         fail(pat);
  20.         /** find match **/
  21.         int pos = posMatch(text, pat);
  22.         if (pos == -1)
  23.             System.out.println("\nNo match found");
  24.         else
  25.             System.out.println("\nMatch found at index "+ pos);
  26.     }
  27.     /** Failure function for a pattern **/
  28.     private void fail(String pat)
  29.     {
  30.         int n = pat.length();
  31.         failure[0] = -1;
  32.         for (int j = 1; j < n; j++)
  33.         {
  34.             int i = failure[j - 1];
  35.             while ((pat.charAt(j) != pat.charAt(i + 1)) && i >= 0)
  36.                 i = failure[i];
  37.             if (pat.charAt(j) == pat.charAt(i + 1))
  38.                 failure[j] = i + 1;
  39.             else
  40.                 failure[j] = -1;
  41.         }
  42.     }
  43.     /** Function to find match for a pattern **/
  44.     private int posMatch(String text, String pat)
  45.     {
  46.         int i = 0, j = 0;
  47.         int lens = text.length();
  48.         int lenp = pat.length();
  49.         while (i < lens && j < lenp)
  50.         {
  51.             if (text.charAt(i) == pat.charAt(j))
  52.             {
  53.                 i++;
  54.                 j++;
  55.             }
  56.             else if (j == 0)
  57.                 i++;
  58.             else
  59.                 j = failure[j - 1] + 1;
  60.         }
  61.         return ((j == lenp) ? (i - lenp) : -1);
  62.     }
  63.     /** Main Function **/
  64.     public static void main(String[] args) throws IOException
  65.     {    
  66.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  67.         System.out.println("Knuth Morris Pratt Test\n");
  68.         System.out.println("\nEnter Text\n");
  69.         String text = br.readLine();
  70.         System.out.println("\nEnter Pattern\n");
  71.         String pattern = br.readLine();
  72.         KnuthMorrisPratt kmp = new KnuthMorrisPratt(text, pattern);        
  73.     }
  74. }

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.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.