string-search - Knuth-Morris-Pratt 字符串搜索算法

Question

我正在使用最后一个函数进行 KMP 字符串搜索的算法......一切似乎都运行良好，除了我认为它不匹配的时候？我没有通过名为 testKMPNotThere 的 JUnit 测试。它断言当在文本中找不到模式时返回的列表应该为空...

所以它应该返回一个 [] 列表，但由于某种原因它返回 [1] 之一.. 我不知道为什么它在找不到模式时添加 1..

这是我的代码-

public List<Integer> kmp(CharSequence pattern, CharSequence text) {
    if (pattern == null || pattern.length() == 0) {
        throw new IllegalArgumentException("No pattern to search for.");
    }
    if (text == null) {
        throw new IllegalArgumentException("Text is null");
    }

    List<Integer> matches = new ArrayList<Integer>();
    int[] map = buildFailureTable(pattern);

    int i = 0;
    int j = 0;

    while (i < text.length()) {
        if (text.charAt(i) != pattern.charAt(j)) {
            if (j != 0) {
                j = map[j];
            } else {
                i++;
            }
        } else if (j == pattern.length() - 1) {
            matches.add(i - (pattern.length() - 1));
            j = 0;
        } else {
            i++;
            j++;
        }
    }

    return matches;


}


public int[] buildFailureTable(CharSequence text) {
    if (text == null) {
        throw new IllegalArgumentException("Pattern is null.");
    }
    int i = 2;
    int j = 0;

    int[] failure = new int[text.length()];
    failure[0] = 0;
    failure[1] = 0;

    while (i < text.length()) {
        if (text.charAt(j) == text.charAt(i)) {
            failure[i] = j + 1;
            i++;
            j++;
        } else if (j > 0) {
            j = failure[j - 1];
        } else {
            failure[i] = 0;
            i++;
        }
    }

    return failure;

}