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&#91;i&#93;=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

Your email address will not be published. Required fields are marked *