我正在解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;
}
1条答案
按热度按时间rdrgkggo1#
26不是模的一部分,是散列的一部分。如果我们在算法中把它们分开,那么我们就可以看到它是如何工作的。对于模量,通常一个大的数字就足够了,不一定是一个
long
: