20. KMP PATTERN MATCHING ALGORITHM

Code:

import java.io.*;

import java.util.*;

class KMP

{

private String text,pattern;

private int n,m,fail[ ];

private static int count;

public KMP(String text, String pattern)

{

this.pattern=pattern;

this.text=text;

n =  text.length();

m = pattern.length();

fail=new int[m];

}

public void computeFailFunction( )

{

fail[0] = 0;

int m = pattern.length();

int j = 0;

int i = 1;

while (i < m)

{

if (pattern.charAt(j) == pattern.charAt(i))

{                                              // j + 1 characters match

 fail[i] = j + 1;

 i++;

 j++;

}

else if (j > 0)                 // j follows a matching prefix

j = fail[j - 1];

else

{                               // no match

fail[i] = 0;

i++;

}

}

}

public int KMPMatch ( )

{

computeFailFunction( );

int i = 0;

int j = 0;

while (i < n)

{

count++;

if (pattern.charAt(j) == text.charAt(i))

{

if (j == m - 1)

return i - m + 1; // match

i++;

j++;

}

else if (j > 0)

j = fail[j -1];

else

i++;

}

return -1;                      // no match

}

public int getNoOfComparisons( )

{

  return count;

}

}

class KMPExp

{

public static void main (String args[])throws IOException

{

String text;

String pattern;

Scanner src=new Scanner(System.in);

System.out.print("Enter Text : ");

text=src.next( );

System.out.print("Enter pattern : ");

pattern=src.next( );

KMP obj=new KMP(text, pattern);

int z=obj.KMPMatch( );

if(z!=-1)

       System.out.println(pattern+" is present in "+text+" from index "+z+" to "+ (z+pattern.length()-1));

else System.out.println(pattern +" is not present in "+text);

 System.out.println(" No of comparsions = "+ obj.getNoOfComparisons( ));

}

}

Need the code??

Download Link= https://www.dropbox.com/s/ul9k4u7nn0fa669/KMPExp.txt