문제 소개
문자열 S가 주어졌을 때, 두 번 이상 등장하는 모든 연속된 부분 문자열을 고려해 봅시다. 이때 각 등장 위치는 서로 겹쳐도 무방합니다. 우리의 목표는 이 중에서 가장 길이가 긴 중복 부분 문자열을 찾는 것이며, 만약 중복되는 부분 문자열이 하나도 존재하지 않는다면 빈 문자열을 반환하면 됩니다.
해시 계산 과정에서 값이 매우 커질 수 있기 때문에, 모든 해시 연산은 10^9 + 7로 나눈 나머지(mod)를 기준으로 처리합니다.
예를 들어 입력이 "ababbaba"라면, 출력은 "bab"가 됩니다.
풀이 접근 방식
이 문제는 이진 탐색(Binary Search)과 롤링 해시(Rolling Hash, Rabin-Karp) 기법을 결합하면 효율적으로 해결할 수 있습니다. 먼저 특정 길이 x의 중복 부분 문자열이 존재하는지 해시를 이용해 빠르게 판정하고, 이진 탐색으로 최적의 길이를 좁혀 가는 방식입니다.
핵심 단계 정리
m := 10^9 + 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을 반환하는 곱셈 함수 정의
26의 거듭제곱 값을 미리 저장할 배열 power 정의
ok(x, s): 길이 x의 중복 부분 문자열이 존재하는지 검사하는 함수 정의
x가 0이면 즉시 빈 문자열 반환
해시값별 시작 위치를 저장할 맵(hash) 생성
current := 0으로 초기화한 뒤, i := 0부터 i < x까지 current := add(mul(current, 26), s[i] − 'a')를 반복하여 첫 번째 윈도우의 해시값 계산
hash[current] := {0} (첫 시작 위치 저장)
n := 문자열 s의 길이
i := x부터 i < n까지 슬라이딩 윈도우 방식으로 반복:
current := sub(current, mul(power[x − 1], s[i − x] − 'a')) — 윈도우에서 밀려나는 문자의 기여도 제거
current := add(mul(current, 26), s[i] − 'a') — 새로 들어오는 문자의 기여도 추가
만약 current가 hash에 이미 존재한다면:
hash[current]에 저장된 각 시작 위치 it에 대해, s.substr(it, x)와 s.substr(i − x + 1, x)를 실제 문자열 비교로 검증하여 해시 충돌 여부를 확인
두 문자열이 같다면 해당 부분 문자열 s.substr(it, x)를 반환
그렇지 않다면 hash[current]에 새 위치 i − x + 1을 추가
반복이 끝날 때까지 중복이 발견되지 않으면 빈 문자열 반환 (길이 x의 중복 없음)
메인 로직 (이진 탐색)
ret := 빈 문자열로 초기화
n := 문자열 S의 길이
power := 크기 n의 배열을 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가 빈 문자열이면 high := mid − 1 (더 짧은 길이 탐색)
그렇지 않으면 temp의 길이가 ret보다 클 때 ret := temp로 갱신하고, low := mid + 1 (더 긴 길이 탐색)
최종적으로 ret 반환
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
C++ 구현 예제
#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
시간 복잡도 분석
ok() 함수 한 번의 호출은 슬라이딩 윈도우를 문자열 전체에 대해 한 번 순회하므로 O(n) 시간이 걸립니다. 이진 탐색은 O(log n)번 호출되므로, 전체 시간 복잡도는 평균적으로 O(n log n)입니다. 다만 해시 충돌 시 실제 문자열을 비교하는 검증 단계가 추가되므로, 최악의 경우에는 약간의 오버헤드가 발생할 수 있습니다. 공간 복잡도는 해시 맵과 거듭제곱 배열 저장을 위해 O(n)입니다.