[종만북] 문제: HABIT
문제
문자열 $s$가 주어지면, $s$의 $substring$ $k$번 이상 등장하는 $substring$의 최대 길이를 구하시오.
$k$번 이상 등장하는 $substring$이 존재하지 않으면, $0$을 출력한다.
서론
문자열 문제를 풀기 위한 접미사 배열(suffix array)을 배우고 이것에 대한 장점.
접미사 배열을 만드는 알고리즘 중 그나마 쉬운 맨버-마이어스 알고리즘을 배웁니다.
이후 정렬된 접미사 배열을 이용해 알고리즘 문제를 풉니다.
접미사 배열
문자열의 모든 접미사(suffix)를 사전순(lexicographical order)으로 정렬한 후, 해당 접미사의 시작 인덱스를 저장한 배열을 접미사 배열이라고 합니다.
브루트 포스 방식으로 접미사 배열을 만든다고 치면, 모든 접미사를 생성하는데 $O(n^2)$, 이후 정렬하는데 $O(\log n)$시간으로 총 $O(n^2 \log n)$시간이 걸립니다.
그러나 우리는 접미사 배열을 $O(n)$시간 안에 만들 수 있습니다!!… 하지만 $O(n)$시간 안에 동작하는 알고리즘은 너무 복잡한 편입니다…
따라서 그렇게까지 복잡하지 않으면서, 동작은 빨리 되는 알고리즘인 맨버-마이어스 알고리즘을 배워봅시다.
맨버-마이어스 알고리즘
인터넷에 있는 양질의 글로 설명을 대체합니다.
맨버-마이어스 알고리즘에서 t가 2의 지수승으로 늘어나는 이유 <- 엄청 좋은 글입니다.
맨버-마이어스 알고리즘의 의의
맨버-마이어스 알고리즘을 사용하면 알고리즘 안에서 사용하는 정렬에 따라 시간 복잡도가 달라집니다.
비교 기반 정렬을 사용 시 $O(n (\log n)^2)$, Radix Sort를 사용 시 $O(n \log n)$시간 안에 구현할 수 있습니다.
보통 정렬 구현시 c++의 <algorithm>에서 지원하는 sort()를 많이 이용하기 때문에, 구현의 편의성을 위해 비교 기반 정렬을 선택하는 경우가 많습니다.
알고리즘 구상
브루트 포스
$substring$은 최대 $\frac{n(n+1)}{2}$개 존재합니다.
각 $substring$이 본문에서 몇 번 나타나는지 세려면, 최악의 경우 $O(nk)$시간이 걸립니다.
정리하면, 브루트 포스 방식을 이용하면 $O(n^4)$시간이 걸리는 것을 알 수 있습니다. KMP 알고리즘의 최적화를 이용해도 $O(n^3)$시간이 걸립니다.
따라서 브루트 포스 방식으로는 이 문제를 풀 수 없음을 알 수 있습니다.
접미사 배열을 이용하자
$substring$이 여러 번 출현할 경우 인접한 접미사$s[i…]$들의 접두사로 출현한다는 것을 알 수 있습니다.
ex) string abcabab에 대해 생각해보자
$array = [ab, abab, abcabab, b, bab, bcabab, cabab]$
여기서 $k$개 이상 같은 $substring$이 존재해야 합니다.
그렇다면, $array[index]$과 $index[index + k - 1]$의 공통 접두사의 최대 길이는 몇인가를 구하는 문제로 변형할 수 있습니다.
그 사이에 있는 $array[index’]$에 관해서는 당연히 공통된 접두사가 존재하므로.
문자열 비교를 하는 데 $O(n)$시간, $n - k + 1$번의 index에 대해 문자열 비교를 수행하므로, $O(n^2)$시간이 걸립니다.
알고리즘 설계
과정을 간략히 정의하면 이렇습니다.
- 접미사 배열을 구한다(맨버-마이어스 알고리즘 이용)
- 접미사 배열을 이용해 공통 접두사의 최대 길이를 구합니다.
정리하면, 접미사 배열을 구할 때 $O(n (\log n)^2)$시간, 접미사 배열을 이용해 겹치는 문자열의 최대 길이를 구하는 알고리즘은 $O(n^2)$시간으로 총 $O(n^2)$시간안에 동작하는 것을 알 수 있습니다.
알고리즘 구현
sort()를 쉽게 해주는 Comparator
유틸리티 struct Comparator를 정의합니다.
1
2
3
4
5
6
7
8
9
struct Comparator {
const vector<int> &group;
int t;
Comparator(const vector<int> &_group, int _t) : group(_group), t(_t) {}
bool operator()(int a, int b) {
if (group[a] != group[b]) return group[a] < group[b];
return group[a + t] < group[b + t];
}
};
getSuffixArray()
맨버-마이어스 알고리즘을 이용하여 접미사 배열을 만드는 함수를 정의합니다.
구현하기 너무 어려워서 교과서에 있는 코드를 가져다 썼습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
vector<int> getSuffixArray() {
int n = input.size(), t = 1;
vector<int> group(n + 1); // perm[]을 정렬하기 위한 기준(그룹)
for (int i = 0; i < n; i++) {
group[i] = input[i];
}
group[n] = -1;
vector<int> perm(n); // 접두사의 index들
for (int i = 0; i < n; i++) {
perm[i] = i;
}
while (t < n) {
Comparator compareUsing2T(group, t);
sort(perm.begin(), perm.end(), compareUsing2T);
t *= 2;
if (t >= n) break;
vector<int> newGroup(n + 1);
newGroup[n] = -1;
newGroup[perm[0]] = 0;
for (int i = 0; i < n; i++) {
if (compareUsing2T(perm[i - 1], perm[i])) {
newGroup[perm[i]] = newGroup[perm[i - 1]] + 1;
} else {
newGroup[perm[i]] = newGroup[perm[i - 1]];
}
}
group = newGroup;
}
return perm;
}
commonPrefix()
문자열의 각 index가 주어지면, 그 둘의 공통 접두사의 최대 길이를 구하는 함수를 정의합니다.
1
2
3
4
5
6
int commonPrefix(int i, int j) {
int ret = 0;
for (; i < input.size() && j < input.size() && input[i] == input[j];
i++, j++, ret++) {}
return ret;
}
longestFrequent()
위 함수를 이용해 문자열의 가능한 모든 index에 대해 반복하여 문제의 답을 구합니다.
1
2
3
4
5
6
7
8
int longestFrequent() {
vector<int> a = getSuffixArray();
int ret = 0;
for (int i = 0; i + k <= input.size(); i++) {
ret = max(ret, commonPrefix(a[i], a[i + k - 1]));
}
return ret;
}
최종 코드
여기에서 확인하세요!
알고리즘 개선 방안
짜잔~ 사실 선형시간에 동작합니다
놀랍게도 $O(n^2)$시간이 아닌 $O(n)$시간 알고리즘이 있습니다.
선형 시간에 동작하는 알고리즘은 다음과 같은 구성입니다.
- 접미사 배열을 $O(n)$시간에 만드는 알고리즘을 이용합니다. ex) DC3(Skew) 알고리즘 또는 SA-IS 알고리즘
- LCP배열을 $O(n)$시간에 만드는 알고리즘을 이용합니다. $ex) Kasai 알고리즘$
- 슬라이딩 윈도우를 이용해 LCP 배열의 최솟값들을 $O(n)$시간 안에 구합니다.
시간이 나면 따로 구현해보도록 하겠습니다.