题目
给你一个字符串 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选择素数，然后需要更具测试集去选定。
