Monday, November 14, 2011

String Matching Algorithms (Robin-Karp)

/**
 *
 * @author Lakshman
 */
import java.io.*;
public class RobinKarp
{
    String text = null, pattern = null;
    int m,n,p,q;
    public void preprocessing()
    {
        m=pattern.length();
        n=text.length();
        q=10;
        p=Integer.parseInt(pattern)%q;
        System.out.println("n = "+n+"   m = "+m+"   q = "+q+"   p = "+p+" \n");
    }
    public void string_match() throws IOException
    {
        System.out.print("\nEnter the Numeric string  : ");
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    text = br.readLine();
    System.out.print("\nEnter the pattern to be searched : ");
    pattern = br.readLine();
    preprocessing();
        int i=0,rem;
    for(int s=0;s<=n-m;s++)
    {
            i=0;
            rem=Integer.parseInt(text.substring(s, s+m))%q;
            System.out.println(text.substring(s, s+m)+" --- "+rem);
            if(p==rem)
            {
                while(i<m&&text.charAt(s+i) == pattern.charAt(i))
                    i++;
                if(i==m)
                {
                    System.out.println("\t  The pattern  is found at "+(s+1)+"th location");
                    return;
                }
                else
                    System.out.println("\t Spurious hit");
            }
    }
    System.out.println("The pattern "+pattern+" is not found in the text :"+text);
    }
    public static void main(String args[]) throws IOException
    {
        RobinKarp r=new RobinKarp();
                r.string_match();
    }
}

No comments:

Post a Comment