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.

```
/**
```

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

If you wish to look at all Java Programming examples, go to Java Programs.

« Prev Page - Java Program to Implement Boyer Moore Algorithm

» Next Page - Java Program to Implement Horner Algorithm

Deep Dive @ Sanfoundry: