Thursday, April 14, 2011

Brute Force Pattern Matching


import java.util.*;
class Pattern
{
                 int brute(String text,String pattern)
                {
                                int n = text.length();    //n is the length of text
                                int m = pattern.length(); // m is length of pattern
                                int j;
                                for(int i=0; i <= (n-m); i++)
                                {  
                                                j = 0;
                                                while ((j < m) && (text.charAt(i+j) == pattern.charAt(j)) )  
                                                j++;  
                                                if (j == m)  
                                                                return i;   // match at i
                                }
                                return -1;   // no match
                }// end of brute()

}



public class BruteForce
{
                public static void main(String args[])
                {
                                Pattern s= new Pattern();
                                Scanner d= new Scanner(System.in);
                                System.out.println("Enter the text");
                                String text = d.nextLine();
                                System.out.println("Enter the pattern");
                                String pattern = d.nextLine();
                                System.out.println("Text: " + text);
                                System.out.println("Pattern: " +pattern);
                                int posn = s.brute(text,pattern);
                                if (posn == -1) 
                                                System.out.println("Pattern not found");
                                else  
                                                System.out.println("Pattern starts at posn " + (posn+1));
                }
}


Output:
Enter the text
andrew
Enter the pattern
dre
Text: andrew
Pattern: dre
Pattern starts at posn 3

Enter the text
he is a clown
Enter the pattern
no
Text: he is a clown
Pattern: no
Pattern not found