public class BoyerMoore {
private String needle;
private int[] right;
public BoyerMoore(String needle) {
this.needle = needle;
int R = 256;
right = new int[R];
for(int i = 0; i < R; i++) {
right[i] = -1; //by default, move right-ward 1 position
}
for(int i = 0; i < needle.length(); i++) {
right[needle.charAt(i)] = i; //store the right-most index of needle characters
}
}
public int search(String haystack) {
int M = needle.length();
int N = haystack.length();
int j, i, skip;
for(i = 0; i < N; i+=skip) {
skip = 0;
for(j = M-1; j >= 0; j--) {
if(haystack.charAt(i + j) != needle.charAt(j)) {
skip = j - right[haystack.charAt(i + j)];
if(skip < 1)
skip = 1;
break;
}
}
if(skip == 0) return i;
}
return -1;
}
public static void main(String...args) {
String haystack = "search a needle in a haystack.";
BoyerMoore bm = new BoyerMoore("needle");
System.out.println(bm.search(haystack));
}
}
