最长重复子串
注意的点:
class Solution { public: int n; unsigned long long a=29; unsigned long long my_power(int m){ unsigned long long ans=1; unsigned long long k=a; while(m!=0){ if(m%2==1) ans=ans*k; k=k*k; m=m/2; } return ans; } int check_s(vector<int> &val,int len){ unsigned long long sum=0,cur; for(int i=0;i<len;i++){ sum=a*sum+(unsigned long long)val[i]; } cur=my_power(len); unordered_set<unsigned long long> st; st.insert(sum); for(int i=1;i<=n-len;i++){ sum=sum*a-(unsigned long long )val[i-1]*cur+(unsigned long long )val[i+len-1]; if(st.count(sum)) return i; else st.insert(sum); } return -1; } string longestDupSubstring(string s) { n=s.size(); vector<int> val(n); for(int i=0;i<n;i++) val[i]=s[i]-'a'; int l=1,r=n-1; int k=-1,len; while (l<=r){ int mid=(l+r)>>1; int start= check_s(val,mid); if(start!=-1){ k=start; len=mid; l=mid+1; }else r=mid-1; } if(k==-1) return ""; else return s.substr(k,len); } };