Алгоритм Бойера Мура Ява: Как найти местоположение задом наперед? - PullRequest
Новая
       33

Алгоритм Бойера Мура Ява: Как найти местоположение задом наперед?

0 голосов
/ 17 января 2019

Я пробовал разные способы реализации алгоритма Бойера Мура с помощью Java, и после завершения моей последней реализации я просто хочу сделать это, но на этот раз я хочу искать в обратном направлении. Что-то вроде этого: haystack = "abcdef" и needle = "bc", где стрелка движется справа налево для завершения поиска. Я знаю, что мне нужно изменить пару направлений, но, похоже, я понял это правильно.

Любая помощь? Заранее спасибо

это мой код. 

private int comparisonCount;
int seekLocation(String needle, String haystack) {
    int[] lastOcc;
    int i, j, needleLength, haystackLength;

    String N = needle.toLowerCase();
    String H = haystack.toLowerCase();

    haystackLength = H.length();
    needleLength = N.length();

    lastOcc = computeLastOcc(needle);

    i = 0;
    while (i < (haystackLength - needleLength)) {

        j = needleLength - 1;
        while (N.charAt(j) == H.charAt(i + j)) {
            j--;
            if (j < 0) {
                return (i);
            }
        }
        if (j < lastOcc[H.charAt(i + j)]) {
            i++;
        } else {
            i = i + j - lastOcc[H.charAt(i + j)];
        }
    }
    return -1;
}

public int[] computeLastOcc(String needle) {
    int[] lastOcc = new int[256];

    for (int i = 0; i < lastOcc.length; i++) {
        lastOcc[i] = -1; 
    }

    for (int i = 0; i < needle.length(); i++) {
        lastOcc[needle.charAt(i)] = i; 
    }
    return lastOcc;
}

/**
 * Returns the number of character compares that where performed during the
 * last search.
 *
 * @return the number of character comparisons during the last search.
 */
int getComparisonsForLastSearch() {
    return this.comparisonCount;
}

public static void main(String[] args) {
    BackwardsSearch bws = new BackwardsSearch();
    int find = bws.seekLocation("de", "abcde");
    System.out.println("Location : " + find);
    int totaalComparison = bws.getComparisonsForLastSearch();
    System.out.println("Comparison : " + totaalComparison);
}
...