Program to Implement KMP Algorithm in Java

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.

import java.io.*;
class k_m_p_fun {

    void failure(String p, int f[]) {
        int i = 1;
        int j = 0;
        f[0] = 0;
        int m = p.length();
        while (i < m) {
            if (p.charAt(j) == p.charAt(i)) {
                f[i] = j + 1;
                i++;
                j++;
            } else if (j > 0)
                j = f[j - 1];
            else {
                f[i] = 0;
                i++;
            }
        }
    }

    int KMP(String t, String p, int f[]) {
        failure(p, f);
        int i = 0;
        int j = 0;
        int n = t.length();
        int m = p.length();
        while (i < n) {
            if (p.charAt(j) == t.charAt(i)) {
                if (j == m - 1)
                    return i - m + 2;
                i++;
                j++;
            } else if (j > 0)
                j = f[j - 1];
            else i++;
        }
        return -1;
    }

}

class k_m_p {
    public static void main(String args[])
    throws IOException {
        InputStreamReader input = new InputStreamReader(System.in);
        BufferedReader obj = new BufferedReader(input);
        System.out.println("Enter the string:");
        String s = obj.readLine();
        System.out.println("Enter the string to be searched:");
        String ts = obj.readLine();
        k_m_p_fun f = new k_m_p_fun();
        int u = ts.length();
        int h[] = new int[u];
        int n = f.KMP(s, ts, h);
        if (n != -1)
            System.out.println("Subsring matched at position:" + n);
        else
            System.out.println("No Substring match");
    }
}

/*OUTPUT

Enter the string:
piitnewpanvel
Enter the string to be searched:
pan
Subsring matched at position:8
Process Exit...

*/

One thought on “Program to Implement KMP Algorithm in Java”

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.