JAVA程序设计:最长重复子串(LeetCode:1044)
程序员文章站
2023-12-29 14:21:34
给出一个字符串S,考虑其所有重复子串(S 的连续子串,出现两次或多次,可能会有重叠)。返回任何具有最长可能长度的重复子串。(如果 S不含重复子串,那么答案为""。)示例 1:输入:"banana"输出:"ana"示例 2:输入:"abcd"输出:""提示:2 <= S.length <= 10^5S 由小写英文字母组成。思路:二分长度+哈希,通过二分长度我们可以每次根据固定长度判断是否存在重复子串,而在找重复子串的过程中我们需要进一步优化,通过......
给出一个字符串 S,考虑其所有重复子串(S 的连续子串,出现两次或多次,可能会有重叠)。
返回任何具有最长可能长度的重复子串。(如果 S 不含重复子串,那么答案为 ""。)
示例 1:
输入:"banana"
输出:"ana"
示例 2:
输入:"abcd"
输出:""
提示:
2 <= S.length <= 10^5
S 由小写英文字母组成。
思路:二分长度+哈希,通过二分长度我们可以每次根据固定长度判断是否存在重复子串,而在找重复子串的过程中我们需要进一步优化,通过哈希的方法快速找到当前长度的串是否含有子串。
有一个问题是,为啥我余数用Integer.MAX.VALUE反而会造成哈希冲突?
class Solution {
private String ans;
static final long P = (long)(Math.pow(2,32));
static final long BASE = 26;
public String longestDupSubstring(String S) {
ans = "";
int l = 1, r = S.length();
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid, S))
l = mid + 1;
else
r = mid - 1;
}
return ans;
}
private boolean check(int x, String s) {
int len = s.length();
Set<Long> st = new HashSet<>();
long[] hashValue = new long[len];
hashValue[0] = s.charAt(0) - 'a';
for (int i = 1; i < x; i++)
hashValue[i] = (hashValue[i - 1] * BASE + (s.charAt(i) - 'a')) % P;
st.add(hashValue[x - 1]);
for (int i = x; i < len; i++) {
hashValue[i] = (hashValue[i - 1] * BASE + (s.charAt(i) - 'a')) % P;
long val = (hashValue[i] - hashValue[i - x] * q(BASE, x) % P + P) % P;
if (st.contains(val)) {
ans = s.substring(i - x + 1, i + 1);
return true;
}
st.add(val);
}
return false;
}
private long q(long x, long y) {
long res = 1;
while (y > 0) {
if (y % 2 == 1)
res = res * x % P;
x = x * x % P;
y /= 2;
}
return res;
}
}
本文地址:https://blog.csdn.net/haut_ykc/article/details/107248926