1044. Longest Duplicate Substring
Given a string s, consider all duplicated substrings: (contiguous) substrings of s that occur 2 or more times. The occurrences may overlap.
Return any duplicated substring that has the longest possible length. If s does not have a duplicated substring, the answer is “”.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| class Solution {
vector<long> power;
int mod = 1e9 + 7;
string rabinKarp(int len, string& s) {
if(len == 0) return "";
long hash = 0;
unordered_map<long, vector<pair<int, string>>> lookup;
for(int i = 0; i < len; i++) {
hash = (hash * 26 + (s[i] - 'a')) % mod;
}
lookup[hash].push_back({0, ""});
for(int i = len; i < s.length(); i++) {
hash = ((hash - power[len - 1] * (s[i-len] - 'a')) % mod + mod) % mod;
hash = (hash * 26 + (s[i] - 'a')) % mod;
string subString = "";
if(lookup.count(hash)) {
subString = s.substr(i - len + 1, len);
for(int j = 0; j < lookup[hash].size(); j++) {
if(lookup[hash][j].second == "") {
lookup[hash][j].second = s.substr(lookup[hash][j].first, len);
}
if(lookup[hash][j].second == subString)
return subString;
}
}
lookup[hash].push_back({i - len + 1, subString});
}
return "";
}
public:
string longestDupSubstring(string s) {
int l = 0, r = s.length();
power = vector<long>(r, 1);
for(int i = 1; i < r; i++)
power[i] = power[i-1] * 26 % mod;
string res = "";
while(l <= r) {
int m = l + (r - l) / 2;
string cmp;
if(m == l and l + 1 == r) {
cmp = rabinKarp(m + 1, s);
if(cmp.length() == 0)
cmp = rabinKarp(m,s);
} else {
cmp = rabinKarp(m, s);
}
if(cmp.length() > 0) {
l = m + 1;
if(res.length() < cmp.length())
res = cmp;
} else {
r = m - 1;
}
}
return res;
}
};
|
