I have to implement Boyer Moore, but it has to find the right most occurrence. (So a reverse version of Boyer Moore). Returns index of the right most location where the patterns occurs within the text. Searching * starts at the right end side of the text and proceeds to the first character (left side). I have tried to reverse the for loops and count the amount of occurences, but my code still doesn't work properly. I think it doesn't shift the right way, but I am not sure. This is my code:
public class BoyerMoore {
private final int R; // the radix
private int[] right; // the bad-character skip array
private int ocurrences;
/**
* Preprocesses the pattern string.
*
* @param pat the pattern string
*/
public BoyerMoore(String pat) {
this.R = 256;
// position of rightmost occurrence of c in the pattern
right = new int[R];
for (int c = 0; c < R; c++)
right[c] = -1;
for (int j = 0; j < pat.length(); j++)
right[pat.charAt(j)] = j;
}
/**
* Returns the index of the first occurrrence of the pattern string
* in the text string.
*
* @param txt the text string
* @return the index of the first occurrence of the pattern string
* in the text string; n if no such match
*/
public int search(String txt, String pat) {
int m = pat.length();
int n = txt.length();
int skip;
for (int i = n - m; i >= 0; i -= skip) {
skip = 0;
for (int j = 0; j < n; j++) {
ocurrences++;
if (pat.charAt(j) != txt.charAt(i+j)) {
skip = Math.max(1, j - right[txt.charAt(i+j)]); //Kijk naar die char
break;
}
}
if (skip == 0) return i; // found
}
return n; // not found
}
int getComparisonsForLastSearch() {
return ocurrences;
}
}