Monday, November 14, 2011

String Matching Algorithms (Knuth-Morris-Pratt)

import java.io.*;
public class KMP2
{
    String text = null, pattern = null;
    int m,n,p,q=0,k;
    int pie[];
    KMP2() throws IOException{
        System.out.print("\nEnter the string  : ");
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    text = br.readLine();
    System.out.print("\nEnter the pattern to be searched : ");
    pattern = br.readLine();
        n=text.length();
        m=pattern.length();
        pie=new int[m+1];

    }
    public void compute_prefix()throws IOException
    {
    pie[0]=0;
    k=0;
    for(q=1;q<m;q++)
        {
               while(k>0 && pattern.charAt(k) !=pattern.charAt(q))
                    k=pie[k-1];
               if(pattern.charAt(k)==pattern.charAt(q))
                    k=k+1;
                pie[q]=k;
    }
    }
    public void find_string() throws IOException
    {
    compute_prefix();
        System.out.print(" PI values :  ");
        for(int i=0;i<m;i++)
      System.out.print("  "+pie[i]);
        q=0;
    for(int i=0;i<n;i++)
    {
            while(q>0 && pattern.charAt(q)!=text.charAt(i))
         q=pie[q-1];
            if(pattern.charAt(q)==text.charAt(i))
        q=q+1;
            if(q==m){
        System.out.println("\nPattern occurs at "+(i-m+1)+" position");
                return;
           }
      }
    System.out.println("\nPattern not found");
    }
    public static void main(String args[]) throws IOException
    {
            KMP2 r=new KMP2();
            r.find_string();
    }
}

No comments:

Post a Comment