假设我们有一个字符串S，请考虑出现2次或更多次的所有重复的连续子字符串。（发生的情况可能会重叠。），我们必须找到具有最长可能长度的重复子字符串。如果没有这样的子字符串，则返回一个空白字符串。由于答案可能非常大，因此请返回mod 10 ^ 9 + 7。
因此，如果输入像“ ababbaba”，那么输出将是“ bab”
为了解决这个问题，我们将遵循以下步骤-
m：= 1e9 + 7
定义一个函数add()，这将需要a，b，
return（（a mod m）+（b mod m））mod m
定义一个函数sub()，这将需要a，b，
return（（a mod m）-（b mod m）+ m）mod m
定义一个函数mul()，这将需要a，b，
return（（a mod m）*（b mod m））mod m
定义阵列幂
定义一个函数ok()，它将取x，s，
如果x等于0，则-
返回空字符串
定义一个称为哈希的映射
当前：= 0
对于初始化i：= 0，当i <x时，更新（将i增加1），执行-
当前：=添加（mul（当前，26），s [i]-'a'）
hash [current]：=定义一个数组(1,0)
n：= s的大小
对于初始化i：= x，当i <n时，更新（将i增加1），执行-
在哈希的末尾插入i-x +1 [当前]
对于在hash [current]中的所有-
将s的子字符串从它返回到x-1
如果从s到x-1的s子字符串与从i-x +1到x-1的s的子字符串相同，则-
当前：= sub（当前，mul（幂[x-1]，s [i-x]-'a'））
当前：=添加（mul（当前，26），s [i]-'a'）
如果count是hash的成员，则-
除此以外
返回空字符串
从主要方法中，执行以下操作-
ret：=空字符串
n：= S的大小
power：=定义一个大小为n的数组，并用1填充它
对于初始化i：= 1，当i <n时，更新（将i增加1），-
power [i]：= mul（power [i-1]，26）
低：= 0，高：= n-1
当低<=高时，执行-
如果temp的大小> ret的大小，则-
低：=中+ 1
ret：=临时
高：=中-1
中：=低+（高-低）/ 2
温度：= ok(mid,S)
如果temp的大小等于0，则-
除此以外
返回ret
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int m = 1e9 + 7;
int add(lli a, lli b){
return ((a % m) + (b % m)) % m;
}
int sub(lli a, lli b){
return ((a % m) - (b % m) + m) % m;
}
int mul(lli a, lli b){
return ((a % m) * (b % m)) % m;
}
vector<int> power;
string ok(int x, string s){
if (x == 0)
return "";
unordered_map<int, vector<int> > hash;
lli current = 0;
for (int i = 0; i < x; i++) {
current = add(mul(current, 26), s[i] - 'a');
}
hash[current] = vector<int>(1, 0);
int n = s.size();
for (int i = x; i < n; i++) {
current = sub(current, mul(power[x - 1], s[i - x] -
'a'));
current = add(mul(current, 26), s[i] - 'a');
if (hash.count(current)) {
for (auto& it : hash[current]) {
if (s.substr(it, x) == s.substr(i - x + 1, x)) {
return s.substr(it, x);
}
}
} else {
hash[current].push_back(i - x + 1);
}
}
return "";
}
string longestDupSubstring(string S){
string ret = "";
int n = S.size();
power = vector<int>(n, 1);
for (int i = 1; i < n; i++) {
power[i] = mul(power[i - 1], 26);
}
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
string temp = ok(mid, S);
if (temp.size() == 0) {
high = mid - 1;
} else {
if (temp.size() > ret.size())
ret = temp;
low = mid + 1;
}
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.longestDupSubstring("ababbaba"));
}"ababbaba"
输出结果
bab