数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中最长重复子串
假设我们有一个字符串S，考虑所有出现2次或更多次的重复连续子串。（这些出现可以重叠），我们需要找到长度最长的重复子串。如果没有这样的子串，则返回空字符串。由于答案可能非常大，因此返回模10^9 + 7的结果。
因此，如果输入为“ababbaba”，则输出为“bab”。
为了解决这个问题，我们将遵循以下步骤：
m := 1e9 + 7
定义一个函数add()，它将接收a, b，
返回((a mod m) + (b mod m)) mod m
定义一个函数sub()，它将接收a, b，
返回((a mod m) - (b mod m) + m) mod m
定义一个函数mul()，它将接收a, b，
返回((a mod m) * (b mod m)) mod m
定义一个数组power
定义一个函数ok()，它将接收x, s，
如果x等于0，则：
返回空字符串
定义一个名为hash的map
current := 0
对于初始化i := 0，当i < x时，更新（i增加1），执行：
current := add(mul(current, 26), s[i] - 'a')
hash[current] := 定义一个数组(1, 0)
n := s的大小
对于初始化i := x，当i < n时，更新（i增加1），执行：
current := sub(current, mul(power[x - 1], s[i - x] - 'a'))
current := add(mul(current, 26), s[i] - 'a')
如果count是hash的成员，则：
对于hash[current]中的所有it：
如果s从it到x - 1的子串与s从i - x + 1到x - 1的子串相同，则：
返回s从it到x - 1的子串
否则
将i - x + 1插入到hash[current]的末尾
返回空字符串
在主方法中，执行以下操作：
ret := 空字符串
n := S的大小
power := 定义一个大小为n的数组并用1填充它
对于初始化i := 1，当i < n时，更新（i增加1），执行：
power[i] := mul(power[i - 1], 26)
low := 0, high := n - 1
当low <= high时，执行：
mid := low + (high - low) /2
temp := ok(mid, S)
如果temp的大小等于0，则：
high := mid - 1
否则
如果temp的大小 > ret的大小，则：
ret := temp
low := mid + 1
返回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
浏览量：563
