접미사 배열
Suffix Array:
0: banana
1: anana
2: nana
3: ana
4: na
5: a- 사전순으로 정렬하면 다음과 같다.
Suffix Array:
5: a
3: ana
1: anana
0: banana
4: na
2: nana
Naive Method
- 모든 접미사 문자열에 대해 비교한 경우: 비교할 때 O(N) 이 걸리고, 정렬할 경우 O(N*log(N)) 이 걸린다.
- 다음과 같은 방법으로 접미사 배열을 얻을 경우 O(N^2 * log(N)) 의 시간 복잡도를 갖는다.
- 일반적으로 문자열의 접미사를 모두 저장하기 보다는 접미사의 시작 위치만 저장하여 메모리를 절약한다.
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
struct NaiveComparator {
const string& s;
NaiveComparator(const string& s) : s(s) {}
bool operator() (int i, int j) {
const char* ptr = s.c_str();
return strcmp(ptr + i, ptr + j) < 0;
}
};
// O(N^2 * log(N)), where N is the length of the given string.
vector<int> getSuffixArray(const string& s) {
vector<int> sfx(s.size());
generate(sfx.begin(), sfx.end(), [x=0]() mutable { return x++; });
sort(sfx.begin(), sfx.end(), NaiveComparator(s));
return sfx;
}
int main() {
string s = "banana";
vector<int> sfx = getSuffixArray(s);
return 0;
}
Manber-Myers Algorithm
- 접미사 배열 생성 시, O(N * log(N)^2) 의 시간복잡도를 갖는다.
- 아이디어는 정렬 시 매 비교마다 각 접미사의 t번째 글자를 기준으로 정렬을 해주는 것이다. 이 때 t는 2배씩 증가한다.
- 정렬을 여러 번 하는데도 빠르게 동작하는 이유는 이전에 비교한 결과를 이용하여 두 문자열의 대소비교를 O(1) 만에 끝낼 수 있기 때문이다. 즉, 정렬할 때 두 문자열의 모든 문자들을 살펴볼 필요가 없다.
- 아래에서 사용된 group[i]은 s[i]부터 시작하는 접미사가 속한 그룹으로, 첫 글자가 같으면 같은 그룹 번호를 가지는 것으로 시작한다. 따라서 초기값은 별도의 번호 없이 s[i]를 그룹 번호로 가진다.
- 그리고 매 t번째 글자를 기준으로 정렬한 후, t번째 글자가 같은 것끼리 같은 그룹으로 묶는다. 즉, 처음 나뉜 그룹에서 인접한 접미사들이 다음 글자마다 그룹핑되는 것이다.
- 매 정렬 후, 새 그룹 번호를 할당하는 이유는 t번째 글자마다 그룹핑을 다시하기 때문이다.
- 비교되는 두 문자열 중 하나가 t보다 짧은 경우를 대비하여 group[n] = -1로 고정시켜놓음으로써 항상 i+t 와 j+t 가 n을 넘기지 않도록 해놓는다. t가 길이를 넘기기 이전에 맨 앞으로 보내지기 때문에 operator() 함수의 if문에서 필터링된다.
- t = 1 일 때 정렬하면, 첫 글자가 같은 접미사들은 sfx 배열 내에서 인접한 위치에 있게 된다.
- t = 2 일 때 정렬하면, 이미 첫 글자가 같은 접미사는 같은 그룹이므로 두번째 글자만 비교하여 순서가 바뀌게 된다.
- 4 < t < n 인 동안 위와 같이 계속 반복한다.
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
struct Comparator {
vector<int> group;
int t;
Comparator(vector<int>& group, int t) : group(group), t(t) {}
bool operator() (int i, int j) {
if (group[i] != group[j]) return group[i] < group[j];
return group[i+t] < group[j+t];
}
};
// O(N * log(N))
vector<int> getSuffixArray(const string& s) {
int n = s.size(), t = 1;
vector<int> group(n+1, -1), sfx(n);
for (int i = 0; i < n; i++) {
group[i] = s[i];
sfx[i] = i;
}
while (t < n) {
Comparator comparator(group, t);
sort(sfx.begin(), sfx.end(), comparator);
t *= 2;
vector<int> newGroup(n+1, -1);
newGroup[sfx[0]] = 0;
for (int i = 1; i < n; i++) {
newGroup[sfx[i]] = newGroup[sfx[i-1]];
// 사전순으로 앞에 위치하면 현재 그룹 번호를 이전 그룹 번호보다 1 증가
if (comparator(sfx[i-1], sfx[i])) newGroup[sfx[i]]++;
}
group = newGroup;
}
return sfx;
}
int main() {
string s = "banana";
vector<int> sfx = getSuffixArray(s);
return 0;
}- 중간 결과를 출력해보면 t 가 증가할 때마다 정렬 결과가 변경되는 것을 알 수 있다.
더보기
Initial: 0 1 2 3 4 5
Suffix Array:
0: banana
1: anana
2: nana
3: ana
4: na
5: a
[t = 1] sfx: 5 1 3 0 2 4
Suffix Array:
5: a
1: anana
3: ana
0: banana
2: nana
4: na <--- 아직 첫번째 글자만 비교했기 때문에 na 는 뒤에 있다.
----------------
[t = 2] sfx: 5 3 1 0 4 2
Suffix Array:
5: a
3: ana
1: anana
0: banana
4: na <--- 두번째 글자를 비교한 후 na가 앞으로 옮겨졌다.
2: nana
----------------
[t = 4] sfx: 5 3 1 0 4 2
Suffix Array:
5: a
3: ana
1: anana
0: banana
4: na
2: nana
----------------- "mississipi" 에서 t번째 글자마다 그룹핑을 다시하여 그룹 번호가 변경된다.
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
struct Comparator {
vector<int> group;
int t;
Comparator(vector<int>& group, int t) : group(group), t(t) {}
bool operator() (int i, int j) {
if (group[i] != group[j]) return group[i] < group[j];
return group[i+t] < group[j+t];
}
};
vector<int> getSuffixArray(const string& s) {
int n = s.size(), t = 1;
vector<int> group(n+1, -1), sfx(n);
for (int i = 0; i < n; i++) {
group[i] = s[i]-'a';
sfx[i] = i;
}
// DEBUG
cout << "Initial: ";
for (int i = 0; i < n; i++) cout << sfx[i] << " ";
cout << endl << "Suffix Array:" << endl;
for (auto i : sfx) cout << "Group[" << i << "] = " << group[i] << ": " << s.substr(i) << endl;
cout << endl;
while (t < n) {
Comparator comparator(group, t);
sort(sfx.begin(), sfx.end(), comparator);
t *= 2;
vector<int> newGroup(n+1, -1);
newGroup[sfx[0]] = 0;
for (int i = 1; i < n; i++) {
newGroup[sfx[i]] = newGroup[sfx[i-1]];
if (comparator(sfx[i-1], sfx[i])) newGroup[sfx[i]]++;
}
// DEBUG
cout << "t = " << t << ": ";
for (int i = 0; i < n; i++) cout << sfx[i] << " ";
cout << endl << "Suffix Array:" << endl;
for (auto i : sfx) cout << "Group[" << i << "] = " << group[i] << ": " << s.substr(i) << endl;
cout << "----------------" << endl;
group = newGroup;
}
return sfx;
}
int main() {
string s = "mississipi";
vector<int> sfx = getSuffixArray(s);
return 0;
}더보기
Initial: 0 1 2 3 4 5 6 7 8 9
Suffix Array:
Group[0] = 12: mississipi
Group[1] = 8: ississipi
Group[2] = 18: ssissipi
Group[3] = 18: sissipi
Group[4] = 8: issipi
Group[5] = 18: ssipi
Group[6] = 18: sipi
Group[7] = 8: ipi
Group[8] = 15: pi
Group[9] = 8: i
t = 2: 9 7 1 4 0 8 3 6 2 5
Suffix Array:
Group[9] = 8: i
Group[7] = 8: ipi
Group[1] = 8: ississipi
Group[4] = 8: issipi
Group[0] = 12: mississipi
Group[8] = 15: pi
Group[3] = 18: sissipi
Group[6] = 18: sipi
Group[2] = 18: ssissipi
Group[5] = 18: ssipi
----------------
t = 4: 9 7 1 4 0 8 6 3 5 2
Suffix Array:
Group[9] = 0: i
Group[7] = 1: ipi
Group[1] = 2: ississipi <---- 같은 그룹 내에서 4번째 글자 기준으로 그룹핑이 다시 된다.
Group[4] = 2: issipi
Group[0] = 3: mississipi
Group[8] = 4: pi
Group[6] = 5: sipi
Group[3] = 5: sissipi
Group[5] = 6: ssipi
Group[2] = 6: ssissipi
----------------
t = 8: 9 7 4 1 0 8 6 3 5 2
Suffix Array:
Group[9] = 0: i
Group[7] = 1: ipi
Group[4] = 2: issipi
Group[1] = 2: ississipi
Group[0] = 3: mississipi
Group[8] = 4: pi
Group[6] = 5: sipi
Group[3] = 6: sissipi
Group[5] = 7: ssipi
Group[2] = 8: ssissipi
----------------
t = 16: 9 7 4 1 0 8 6 3 5 2
Suffix Array:
Group[9] = 0: i
Group[7] = 1: ipi
Group[4] = 2: issipi
Group[1] = 3: ississipi
Group[0] = 4: mississipi
Group[8] = 5: pi
Group[6] = 6: sipi
Group[3] = 7: sissipi
Group[5] = 8: ssipi
Group[2] = 9: ssissipi
----------------
최장 공통 접두사 배열
- 접미사 배열에서 이전 접미사와 공통되는 접두사의 길이를 저장한 배열이다. by Wikipedia
- 알고리즘 대회에서는 어떤 문자열이 주어질 때 2번 이상 반복되는 연속되는 부분 문자열의 최대 갈이를 구할 때 주로 사용된다.
- 해결책은 어떤 부분 문자열은 주어진 문자열의 접미사의 접두사라는 점을 이용하여 인접한 접미사끼리 공통되는 부분 중 가장 긴 것을 찾아내는 것이다.
- LCP 배열의 경우, 문자열의 길이가 길면 접미사를 비교하는데 시간이 오래걸리는 점을 보완하기 위해 인접한 접미사끼리 비교할 때 공통되는 문자들은 건너뛰어 시간을 절약한다. 예를 들면, mississipi 에서 접미사 ipi 와 issipi 를 비교할 때 이전에 i와 ipi 가 비교되었기 때문에 i는 세지 않고 바로 다음 글자인 p와 s부터 길이를 측정하는 것이다.
- 주의할 점은 LCP 배열을 만들 때, 문자열 비교 시간을 절약하기 위해 첫번째 위치에서부터 비교해야 하므로 prevSfx 처럼 접미사 배열에서 이전 접미사의 위치를 저장할 필요가 있다. 0번째 접미사는 이전 접미사가 없으므로 -1을 저장한다.
// 위와 동일
vector<int> getLongestCommonPrefix(const string& s, const vector<int>& sfx) {
int n = s.size();
vector<int> plcp(n), prevSfx(n), lcp(n);
prevSfx[sfx[0]] = -1;
for (int i = 1; i < n; i++) prevSfx[sfx[i]] = sfx[i-1];
for (int i = 0, common = 0; i < n; i++) {
if (prevSfx[i] == -1) plcp[i] = 0;
else {
while (s[i+common] == s[prevSfx[i]+common]) common++;
plcp[i] = common;
if (common > 0) common--;
}
}
for (int i = 0; i < n; i++) lcp[i] = plcp[sfx[i]];
return lcp;
}
int main() {
string s = "mississipi";
vector<int> sfx = getSuffixArray(s);
for (int x : sfx) cout << s.substr(x) << endl;
vector<int> lcp = getLongestCommonPrefix(s, sfx);
int maxLen = 0, start = 0;
for (int i = 0; i < lcp.size(); i++) {
if (maxLen < lcp[i]) {
maxLen = lcp[i];
start = i;
}
}
cout << "LongestCommonPrefix: " << s.substr(start, maxLen) << endl;
return 0;
}
/*
i
ipi
issipi
ississipi
mississipi
pi
sipi
sissipi
ssipi
ssissipi
LongestCommonPrefix: issi
*/- 소스 코드: 익명 함수 사용 시, 훨씬 빠르다.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<int> getSuffixArray(const string& s) {
int n = s.size();
vector<int> g(n+1, -1), sfx(n), ng;
for (int i = 0; i < n; i++) { g[i] = s[i]; sfx[i] = i; }
for (int t = 1; t < n; t <<= 1, g = ng) {
auto cmp = [&](int i, int j)->bool {
if (g[i] != g[j]) return g[i] < g[j];
return g[i+t] < g[j+t];
};
sort(sfx.begin(), sfx.end(), cmp);
ng.clear(); ng.resize(n+1, -1); ng[sfx[0]] = 0;
for (int i = 1; i < n; i++) {
ng[sfx[i]] = ng[sfx[i-1]];
if (cmp(sfx[i-1], sfx[i])) ng[sfx[i]]++;
}
}
return sfx;
}
vector<int> getLongestCommonPrefix(const string& s, const vector<int>& sfx) {
int n = s.size();
vector<int> plcp(n), prevSfx(n), lcp(n);
prevSfx[sfx[0]] = -1;
for (int i = 1; i < n; i++) prevSfx[sfx[i]] = sfx[i-1];
for (int i = 0, common = 0; i < n; i++) {
if (prevSfx[i] == -1) plcp[i] = 0;
else {
while (s[i+common] == s[prevSfx[i]+common]) common++;
plcp[i] = common;
if (common > 0) common--;
}
}
for (int i = 0; i < n; i++) lcp[i] = plcp[sfx[i]];
return lcp;
}
int main() {
string s; cin >> s;
vector<int> sfx = getSuffixArray(s);
vector<int> lcp = getLongestCommonPrefix(s, sfx);
for (int x : sfx) cout << x+1 << " ";
cout << endl << "x" << " ";
for (int i = 1; i < lcp.size(); i++) cout << lcp[i] << " ";
cout << endl;
return 0;
}
'Algorithm > Theory' 카테고리의 다른 글
| 이분 탐색 + 매개변수 탐색 (0) | 2021.03.13 |
|---|---|
| 계산기하 - vector 연산 (0) | 2020.02.23 |
| 소인수분해, 소수 판별법, 에라토스테네스의 체 (0) | 2019.05.16 |
