Rabin-Karp字符串匹配

Question

我正在学习算法，并实现了拉宾-卡普字符串搜索算法。我没有实现滚动HashCode，但这位在线法官认为它是正确的。

它比str.indexOf()实现慢(7ms，而不是4ms)。这是否可以改善呢？这方面的时间复杂性是多少？

class Solution {
public int strStr(String haystack, String needle) {
    if (haystack == null || needle == null)
        return -1;
    int needleHash = hashCode(needle);
    int plen = needle.length();
    boolean t = true;
    int tlen = haystack.length() - needle.length() + 1;
    for (int i = 0; i < tlen; i++) {
        String sub = haystack.substring(i, plen + i);
        int haystackHash = hashCode(sub);
        if (haystackHash == needleHash) {
            for (int j = 0; j < plen; j++) {
                char[] charN = needle.toCharArray();
                char[] charH = sub.toCharArray();
                if (charN[j] != charH[j]) {
                    t = false;
                }
            }
            if (t == true) {
                return i;
            }
        }
    }
    return -1;
}

public int hashCode(String value) {
    int h = 777;
    if (value.length() > 0) {
        char val[] = value.toCharArray();

        for (int i = 0; i < val.length; i++) {
            h = 31 * h + val[i];
        }
    }
    return h;
  }
}

Answer 1

您缺少了使用滚动散列的基本好处：

for (int i = 0; i < tlen; i++) {
    String sub = haystack.substring(i, plen + i);
    int haystackHash = hashCode(sub);

这里，我们研究了plen在每个字符位置上的特征，即O(mn)，其中m是干草堆长度，n是针头长度。

通过使用滚动散列，我们只需要在循环中每次检查两个字符(一个添加到哈希，另一个从其中删除)。这当然是O(m)，这大大提高了效率时，n是大。

只有当有散列匹配时，才检查子字符串，这种匹配应该是不频繁的。

其他问题：

• 为什么将needle和sub转换为char数组来比较它们？当然，您不希望每次在j循环中都这样做；如果编写if (sub == needle) return i;，甚至不需要这个循环。
• if (t == true)更简单地写成了if (t)，因为这是t能够保存的唯一真值。同样，在消除j循环时不需要。

改进的代码

你想写些更像这样的东西：

public int strStr(final String haystack, final String needle)
{
    if (haystack == null || needle == null)
        return -1;

    final int nlen = needle.length();
    final int hlen = haystack.length();
    if (nlen > hlen)
        return -1;

    int needleHash = 0;
    int hash_remove = 1;
    for (char c: needle.toCharArray()) {
        needleHash = addHash(needleHash, c);
        hash_remove = addHash(hash_remove, '\0');
    }

    int haystackHash = 0;
    for (int i = 0;  i < nlen - 1;  ++i) {
        haystackHash = addHash(haystackHash, haystack.charAt(i));
    }

    for (int i = 0;  i + nlen < hlen;  ++i) {
        haystackHash = addHash(haystackHash, haystack.charAt(i + nlen));
        if (haystackHash == needleHash && haystack.substring(i, i+nlen) == needle)
            return i;
        haystackHash -= haystack.charAt(i) * hash_remove;
    }

    return -1;
}

private int addHash(int h, char c)
{
    // calculation may overflow, but that's fine
    return 31 * h + c;
}

唯一的法宝是hash_remove的计算和使用，以撤消移出匹配窗口的字符的影响。