Giả sử chúng ta có một chuỗi S, hãy xem xét tất cả các chuỗi con liền kề trùng lặp xảy ra từ 2 lần trở lên. (Các lần xuất hiện có thể trùng nhau.), Chúng ta phải tìm ra chuỗi con trùng lặp có độ dài dài nhất có thể. Nếu không có chuỗi con như vậy, thì trả về một chuỗi trống. Vì câu trả lời có thể rất lớn, vì vậy hãy quay lại trong mod 10 ^ 9 + 7.
Vì vậy, nếu đầu vào giống như "ababbaba", thì đầu ra sẽ là "bab"
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
m:=1e9 + 7
-
Xác định một hàm add (), điều này sẽ lấy a, b,
-
return ((a mod m) + (b mod m)) mod m
-
Xác định một hàm sub (), điều này sẽ lấy a, b,
-
return ((a mod m) - (b mod m) + m) mod m
-
Xác định một hàm mul (), điều này sẽ nhận a, b,
-
return ((a mod m) * (b mod m)) mod m
-
Xác định sức mạnh mảng
-
Xác định một hàm ok (), điều này sẽ lấy x, s,
-
nếu x giống 0 thì -
-
trả về chuỗi trống
-
-
Xác định một bản đồ được gọi là băm
-
hiện tại:=0
-
để khởi tạo i:=0, khi i
-
current:=add (mul (current, 26), s [i] - 'a')
-
-
hash [current]:=Xác định mảng (1, 0)
-
n:=kích thước của s
-
để khởi tạo i:=x, khi i
-
current:=sub (current, mul (power [x - 1], s [i - x] - 'a'))
-
current:=add (mul (current, 26), s [i] - 'a')
-
nếu số đếm là thành viên của băm, thì -
-
cho tất cả nó trong hash [current] -
-
nếu chuỗi con của s từ nó đến x - 1 giống với chuỗi con của s từ i - x + 1 đến x- 1, thì -
-
trả về chuỗi con của s từ nó thành x - 1
-
-
-
-
Nếu không
-
chèn i - x + 1 vào cuối hàm băm [hiện tại]
-
-
-
trả về chuỗi trống
-
Từ phương thức chính, thực hiện như sau -
-
ret:=chuỗi trống
-
n:=kích thước của S
-
power:=Xác định một mảng có kích thước n và điền vào đây là 1
-
để khởi tạo i:=1, khi i
-
power [i]:=mul (power [i - 1], 26)
-
-
thấp:=0, cao:=n - 1
-
trong khi thấp <=cao, làm -
-
giữa:=low + (cao - thấp) / 2
-
temp:=ok (giữa, S)
-
nếu kích thước của nhiệt độ bằng 0, thì -
-
cao:=giữa - 1
-
-
Nếu không
-
nếu kích thước của nhiệt độ> kích thước của ret, thì -
-
ret:=temp
-
-
thấp:=mid + 1
-
-
-
trả lại ret
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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"));
} Đầu vào
"ababbaba"
Đầu ra
bab