1

根据工作伙伴的说法，以下实现 boyer moore 算法的效率不是很高。我似乎不知道我做错了什么，没有得到高质量的结果。

我已经对其进行了测试，并且效果很好，我唯一需要做的就是高效地工作。我可以得到任何帮助吗？

这是.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;
}
4

0 回答 0