leetcode 1044最长重复子串(关于模的小问题)

2sbarzqh 于 2021-07-04 发布在 Java

关注(0)|答案(1)|浏览(278)

我正在解leetcode 1044，答案是使用二进制搜索和滚动哈希。基本上使用二进制搜索来选择一个长度，然后搜索该长度的重复字符串。这里使用滚动哈希来节省空间（不是使用集合来存储所有子字符串，而是存储子字符串的哈希）。这就是解决方案的背景。
我的问题是用模数来防止溢出。我选择了long.max\u值，我相信它足够大，可以处理它，但是当我使用long.max\u值时，答案是不正确的。但是，当我使用long.max\u value/26或math.pow（2，32）时，它们都可以工作。对不起，我对模数很不满意，我想我肯定错过了一些东西。有人能解释一下吗？谢谢！以下是我的解决方案：

public static long modulus = Long.MAX_VALUE / 26;
public String longestDupSubstring(String S) {
    int n = S.length();
    int l = 1;
    int r = n - 1;
    int index = -1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        int temp = findDuplicate(S, m);
        if (temp != -1) {
            index = temp;
            l = m + 1;
        }
        else {
            r = m - 1;
        }
    }
    return index == -1 ? "" : S.substring(index, index + r);
}
private int findDuplicate(String s, int len) {
    Set<Long> set = new HashSet<>();
    long hash = 0;
    long p = 1;
    for (int i = 0; i < len; i++) {
        hash = (hash * 26 + s.charAt(i) - 'a') % modulus;
        p = (p * 26) % modulus;
    }
    set.add(hash);

    for (int i = len; i < s.length(); i++) {
        hash = (hash * 26 + (s.charAt(i) - 'a')
                - (s.charAt(i - len) - 'a') * p) % modulus;
        if (hash < 0) {
            hash += modulus;
        }
        if (set.contains(hash)) {
            return i - len + 1;
        }
        set.add(hash);
    }
    return -1;
}

Java Math Hash modulus rabin-karp

来源：https://stackoverflow.com/questions/63766278/leetcode-1044-longest-duplicate-substring-small-question-in-terms-of-modulus

1条答案

按热度按时间

rdrgkggo1#

26不是模的一部分，是散列的一部分。如果我们在算法中把它们分开，那么我们就可以看到它是如何工作的。对于模量，通常一个大的数字就足够了，不一定是一个 long :

public final class Solution {
    int a = 26;
    int mod = 1 << 29;

    public final String longestDupSubstring(
        final String s
    ) {
        int lo = 1;
        int hi = s.length() - 1;

        while (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1);
            int startIndex = search(s, mid);

            if (startIndex == - 1) {
                hi = mid - 1;
            }

            else {
                lo = -~mid;
            }
        }

        int startIndex = search(s, hi);
        return startIndex == -1 ? "" : s.substring(startIndex, startIndex + hi);
    }

    public final int search(
        final String s,
        final int len
    ) {
        long h = 0;
        long aL = 1;

        for (int i = 0; i < len; i++) {
            h = (h * a % mod + s.charAt(i)) % mod;
            aL = aL * a % mod;
        }

        HashMap<Long, List<Integer>> visited = new HashMap<>();
        visited.put(h, new ArrayList<Integer>());
        visited.get(h).add(0);

        for (int i = 1; i < -~s.length() - len; i++) {
            h = ((h * a % mod - s.charAt(i - 1) * aL % mod + mod) % mod + s.charAt(i + len - 1)) % mod;

            if (visited.containsKey(h)) {
                for (int start : visited.get(h)) {
                    if (s.substring(start, start + len).equals(s.substring(i, i + len))) {
                        return i;
                    }
                }

            } else {
                visited.put(h, new ArrayList<Integer>());
            }

            visited.get(h).add(i);
        }

        return -1;
    }
}

赞(0）回复(0）举报 2021-07-04

我来回答

leetcode 1044最长重复子串(关于模的小问题)

1条答案

相关问题

热门标签

最新问答