leetcode 1044. 最长重复子串（字符串hash）

题意：

给出一个字符串 S，考虑其所有重复子串（S 的连续子串，出现两次或多次，可能会有重叠）。

返回任何具有最长可能长度的重复子串。（如果 S 不含重复子串，那么答案为 ""。）

示例 1：

输入："banana"
输出："ana"

示例 2：

输入："abcd"
输出：""

思路：（字符串hash+二分）

针对长度简单的从length(S)-1递减时间过长的问题。如果有长度为L的最长重复子串，则必然有L_0<L的重复子串，因此先采用二分法寻找到最长重复子串的长度。

51nod2619也利用了字符串hash

 1 typedef unsigned long long ull;
 2 const int N=1e5+10;
 3 const ull base=23333;
 4 class Solution {
 5 public:
 6     ull _hash[N],p[N];
 7     ull get(int l,int r){
 8         return _hash[r]-_hash[l-1]*p[r-l+1];
 9     }
10     void init(string s){
11         p[0]=1;
12         for(int i=1;i<=s.size();i++){
13             p[i]=p[i-1]*base;
14             _hash[i]=_hash[i-1]*base+s[i-1]-'a';
15         }
16     }
17     int check(int mid,int len){
18         unordered_map<ull,bool>mp;
19         for(int i=1;i+mid-1<=len;i++){
20             ull k=get(i,i+mid-1);
21             if(mp.find(k)!=mp.end())return i;
22             mp[k]=true;
23         }
24         return 0;
25     }
26     string longestDupSubstring(string S) {
27         init(S);
28         int len=S.size();
29         string ans="";
30         int l=1,r=len-1;
31         while(l<=r){
32             int mid=(l+r)/2;
33             if(check(mid,len))l=mid+1;
34             else r=mid-1;
35         }
36         l--;
37         if(l==-1)return "";
38         int k=check(l,len);
39         return S.substr(k-1,l);
40     }
41 };

View Code