How can I find the right most occurence with the Boyer Moore algorithm?

279 Views Asked by At

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;
}

}

0

There are 0 best solutions below