with trace output

BoyerMoore.java

/**
 * Boyer-Moore string pattern matching
 * 
 * @author Douglas 
 */
import java.util.Map;
import java.util.HashMap;

public class BoyerMoore
{
    private String P,T;
    private int m,n;
    Map<Character, Integer> map = new HashMap<>();
        
    
    public BoyerMoore(String T, String P)
    {
        this.P = P;
        this.T = T;
        m = P.length();
        n = T.length();
        
       for(int i = 0; i < m; i++)
       {
           map.put(P.charAt(i), i);
        }
        
        
    }
    
    private int last(char C)
    {  
        try{
        return map.get(C);
    }
    catch(NullPointerException e){
        return -1;
    }
    
    }

    /**
     * @return     Index of pattern start
     */
    public int BMMatch()
    {   
        int i,j;
        i = j = m - 1;
        
        do{
     
            //Verbose
            System.out.println("\ni = " + i + ", j = " + j);
            
            if(P.charAt(j) == T.charAt(i))
            {
                if(j == 0)
                    return i;
                else{
                    j = j - 1;
                    i = i - 1;
                }
            }
            else{
                System.out.println(" i = " + i + " + " + m + " - min("+j+", 1 + " + P.lastIndexOf(T.charAt(i))+")");
                i = i + m - Math.min(j, 1 + last(T.charAt(i)));
                
                System.out.println("j = " + (m-1));
                j = m - 1;
            }
            
            
        }
        while(i <= n - 1);
        
        return -1;
    }
}