Knuth Morris Pratt Algorithm for Pattern Matching

/**
 ** Java Program to implement Knuth Morris Pratt Algorithm
 **/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class KnuthMorrisPratt
{
    private int[] failure; /** Failure array **/
    private int KeyCount; /** key operation counter **/

    public KnuthMorrisPratt(String text, String pat) /** Constructor **/
    {
        KeyCount = 0;
        failure = new int[pat.length()]; /** pre construct failure array for a pattern **/
        fail(pat);
        int pos = posMatch(text, pat); /** find match **/
        if (pos == -1)
            System.out.println("\nNo match found");
        else {
        System.out.println("\nMatch found at index "+ pos);
        System.out.println("\nNo of comparisons : " + KeyCount );
        }
    }

    /** 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];
            //KeyCount++;
            while ((pat.charAt(j) != pat.charAt(i + 1)) && i >= 0){
            i = failure[i];
            //KeyCount++;
            }


            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)
        {
        KeyCount++;
            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);
    }
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Input-Output:

Knuth Morris Pratt Test

Enter Text

hello how are you

Enter Pattern

are

Match found at index 10

No of comparisons : 13