алгоритм Бойера Мура: сделать его более эффективным с помощью Java - PullRequest
Новая
       31

алгоритм Бойера Мура: сделать его более эффективным с помощью Java

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

По словам коллег по работе, следующая реализация алгоритма Бойера-Мура не очень эффективна. Кажется, я не знаю, что я делаю неправильно, чтобы не получить результат хорошего качества.

Я проверил это, и оно работает очень хорошо, единственное, что мне нужно сделать, это получить работу эффективно. Могу ли я получить помощь с этим?

это реализация кода в .java 

int findLocation(String needle, String haystack) {

    if (needle == null || haystack == null
            || needle.length() > haystack.length()) {
        return -1;
    }

    char[] nNeedle = needle.toCharArray();
    char[] hHaystack = haystack.toCharArray();

    int[] good_shift = new int[nNeedle.length];

    for (int i = 0; i < nNeedle.length; i++) {
        good_shift[i] = goodshift(nNeedle, i);
    }

    int[] bad_shift = new int[MAX_CHARACTERS];
    for (int i = 0; i < MAX_CHARACTERS; i++) {
        bad_shift[i] = nNeedle.length;
    }

    int offset = 0;
    int scan = 0;
    int last = nNeedle.length - 1;
    int maxoffset = hHaystack.length - nNeedle.length;

    for (int i = 0; i < last; i++) {
        bad_shift[nNeedle[i]] = last - 1;
    }

    while (offset <= maxoffset) {
        for (scan = last; nNeedle[scan] == hHaystack[scan + offset]; scan--) {
            if (scan == 0) {
                return offset;
            }
        }
        offset += Math.max(bad_shift[hHaystack[offset + last]], good_shift[last - scan]);
    }
    return -1;
}

int goodshift(char[] needle, int matches) {
    if (matches >= needle.length || matches < 0) {
        return -1;
    }
    if (matches == 0) {
        return 1;
    }

    int max = needle.length - 1;
    int offset = max;
    int last = matches - 1;

    while (offset >= 1) {
        --offset;

        for (int i = 0; (offset - i >= 0) && needle[(max - i)] == needle[(offset - i)]; i++) {
            if ((offset - i) == 0) {
                return max - offset;
            }
            if (i == last) {
                if (needle[(max - matches)] != needle[(offset - matches)]) {
                    return max - offset;
                } else {
                    break;
                }
            }
        }
    }
    return needle.length;
}
...