문자열 S가 있다고 가정하고 2회 이상 발생하는 모든 중복된 연속 하위 문자열을 고려합니다. (중복될 수 있습니다.), 우리는 가능한 가장 긴 길이를 갖는 중복된 부분 문자열을 찾아야 합니다. 그러한 부분 문자열이 없으면 빈 문자열을 반환합니다. 답변이 매우 클 수 있으므로 mod 10^9 + 7로 반환하십시오.
따라서 입력이 "ababbaba"와 같으면 출력은 "bab"이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
m :=1e9 + 7
-
add() 함수를 정의하면, b,
-
return ((a mod m) + (b mod m)) mod m
-
함수 sub()를 정의하면, b,
-
return ((a mod m) - (b mod m) + m) mod m
-
mul() 함수를 정의하면, b,
-
return ((a mod m) * (b mod m)) mod m
-
어레이 전력 정의
-
ok() 함수를 정의합니다. x, s,
-
x가 0과 같으면 -
-
빈 문자열 반환
-
-
해시라는 하나의 맵 정의
-
현재 :=0
-
initialize i :=0의 경우, i
-
현재 :=add(mul(현재, 26), s[i] - 'a')
-
-
hash[current] :=배열 정의 (1, 0)
-
n :=s
의 크기 -
initialize i :=x의 경우, i
-
현재 :=sub(현재, mul(전력[x - 1], s[i - x] - 'a'))
-
현재 :=add(mul(현재, 26), s[i] - 'a')
-
count가 해시의 구성원이면 -
-
hash[current] −
의 모든 것에 대해-
s에서 x - 1까지의 부분 문자열이 i - x + 1에서 x- 1까지의 s의 부분 문자열과 같으면 -
-
x에서 s의 부분 문자열을 반환 - 1
-
-
-
-
그렇지 않으면
-
해시[현재]
끝에 i - x + 1 삽입
-
-
-
빈 문자열 반환
-
기본 방법에서 다음을 수행하십시오 -
-
ret :=빈 문자열
-
n :=S
의 크기 -
power :=크기가 n인 배열을 정의하고 1로 채웁니다.
-
initialize i :=1의 경우, i
-
거듭제곱[i] :=mul(제곱[i - 1], 26)
-
-
낮음 :=0, 높음 :=n - 1
-
낮음 <=높음, 수행 -
-
중간 :=낮음 + (높음 - 낮음) /2
-
온도 :=ok(중간, S)
-
temp의 크기가 0과 같으면 -
-
높음 :=중간 - 1
-
-
그렇지 않으면
-
temp 크기> ret 크기이면 -
-
ret :=임시
-
-
낮음 :=중간 + 1
-
-
-
리턴 렛
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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