1

我必须实现 Boyer Moore，但它必须找到最合适的出现。（所以是 Boyer Moore 的反向版本）。返回文本中出现模式的最右侧位置的索引。搜索 * 从文本的右端开始，一直到第一个字符（左侧）。我试图反转 for 循环并计算出现次数，但我的代码仍然无法正常工作。我认为它不会以正确的方式转变，但我不确定。这是我的代码：

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

}

4

0 回答 0