leetcode-1044：最长重复子串
题目
题目链接
给你一个字符串 s ，考虑其所有 重复子串 ：即，s 的连续子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。
返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 “” 。
示例 1：
输入：s = "banana"
输出："ana"
示例 2：
输入：s = "abcd"
输出：""
解题
方法一：Rabin-Karp(滚动哈希) + 二分搜索
参考链接
最后利用二分查找选择长度，因为如果长度小的子字符串sub1存在，那么它可能是长度大的子字符串sub2的子字符串
如果长度大的子字符串不存在重复，那么更大的子字符串也不可能重复。
class Solution {
public:
uint64_t prime=31;
string longestDupSubstring(string s) {
int n=s.size();
//滚动哈希,查找指定长度的字符串
auto find=[&](int len){
uint64_t hash=0;
uint64_t power=1;
//初始化哈希
for(int i=0;i<len;i++){
hash=hash*prime+s[i]-'a';
power*=prime;
}
//查找哈希是否之前遇到过
unordered_set<uint64_t> set{hash};
for(int i=len;i<n;i++){
hash=hash*prime-power*(s[i-len]-'a')+s[i]-'a';
if(set.count(hash)) return i-len+1;
set.insert(hash);
}
return -1;
};
//二分查找(选则长度)
int l=0;
int r=n-1;
int pos=-1;
int len=0;
while(l<=r){
int mid=(l+r)/2;
int start=find(mid);
if(start!=-1){
len=mid;
pos=start;
l=mid+1;
}
else{
r=mid-1;
}
}
if(pos==-1) return "";
return s.substr(pos,len);
}
};
补充：
unsigned long long 是可以自动取余的,因此不会出现超过上界。为了防止哈希冲突，一般prime选择素数，然后需要更具测试集去选定。