# 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 `""`.

Example 1:

``````Input: s = "banana"
Output: "ana"
``````

Example 2:

``````Input: s = "abcd"
Output: ""
``````

Constraints:

• `2 <= s.length <= 3 * 104`
• `s` consists of lowercase English letters.

``````class Solution {
public:
string longestDupSubstring(string s) {
string res;
int n = s.size(), left = 0, right = n, M = 1e7 + 7;
vector<int> power(n);
for (int i = 0; i < n; ++i) {
power[i] = (i == 0) ? 1 : (power[i - 1] * 26) % M;
}
while (left < right) {
int mid = left + (right - left) / 2;
string dup = rabinKarp(s, mid, power);
if (dup.size() > res.size()) {
res = dup;
left = mid + 1;
} else {
right = mid;
}
}
return res;
}
string rabinKarp(string s, int len, vector<int>& power) {
if (len == 0) return "";
int n = s.size(), cur = 0, M = 1e7 + 7;
unordered_map<int, vector<int>> hash;
for (int i = 0; i < len; ++i) {
cur = (cur * 26 + (s[i] - 'a')) % M;
}
hash[cur] = {0};
for (int i = len; i < n; ++i) {
cur = ((cur - power[len - 1] * (s[i - len] - 'a')) % M + M) % M;
cur = (cur * 26 + (s[i] - 'a')) % M;
if (!hash.count(cur)) {
hash[cur] = {i - len + 1};
} else {
for (int idx : hash[cur]) {
if (s.substr(idx, len) == s.substr(i - len + 1, len)) return s.substr(idx, len);
}
hash[cur].push_back(i - len + 1);
}
}
return "";
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1044

https://leetcode.com/problems/longest-duplicate-substring/

https://leetcode.com/problems/longest-duplicate-substring/discuss/694963/Beats-100-using-Trie-tree

https://leetcode.com/problems/longest-duplicate-substring/discuss/695197/C%2B%2B-Binary-Seach-with-Robin-Karp-Algorithm-O(nlogn)

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation