Thursday, April 14, 2011

Boyer Moore Algorithm


import java.util.*;
class Pattern3
{
                int bmMatch(String text,String pattern)
                {  
                                int last[] = buildLast(pattern);
                                int n = text.length(); 
                                int m = pattern.length();
                                int i = m-1; 
                                if (i > n-1)  
                                                return -1; // no match  
                                int j = m-1;
                                do
                                {   
                                if (pattern.charAt(j) == text.charAt(i)) 
                                                if (j == 0)   
                                                                return i; // match     
                                                else
                                                {
                                                                // looking-glass technique 
                                                                i--;   
                                                                j--;     
                                                } 
                                else
                                {
                                                // character jump technique   
                                                int lo = last[text.charAt(i)]; 
                                                //last occ     
                                                i = i + m - Math.min(j, 1+lo);  
                                                j = m - 1;  
                                }  
                                }
                                while (i <= n-1);
                                                return -1; // no match
                }// end of bmMatch()


                int[] buildLast(String pattern)
                /* Return array storing index of last    occurrence of each ASCII char in pattern. */
                {  
                                int last[] = new int[128];
                                // ASCII char set  
                                for(int i=0; i < 128; i++)  
                                                last[i] = -1;
                                // initialize array  
                                for (int i = 0; i < pattern.length(); i++)
                                                last[pattern.charAt(i)] = i;  
                                return last;
                } // end of buildLast()
}
public class BoyleMoore
{
                public static void main(String args[])
                {
                                Pattern3 s= new Pattern3();
                                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.bmMatch(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
pattern
Enter the pattern
er
Text: pattern
Pattern: er
Pattern starts at posn 5

Enter the text
virtual memory
Enter the pattern
me
Text: virtual memory
Pattern: me
Pattern starts at posn 9