문자열 s의 접미사들을 사전순대로 정렬한 것이다. 정확히는 접미사들의 시작 인덱스들이 저장된다. 접미사들을 싸그리 저장할 수는 없기 때문에..
접미사 배열 구현
브루트포스 O(n^2logn)
vector<int> suffixArray(const string& s) {
int n = s.size();
vector<int> ret(n);
for (int i=0; i<n; ++i) ret[i]= i;
sort(ret.begin(), ret.end(), [const string& s]
(int i, int j) {
return strcmp(s.c_str()+i, s.c_str()+j) < 0;
});
return ret;
}말 그대로 idx번째부터 문자열을 포인터로 받아서 비교하교 정렬한다.
정렬 nlogn * 문자열비교 n = n^2logn
멘버 마이어스 O(n * (logn)^2)
struct Comp{
const vector<int>& group;
int t;
Comp(const vector<int>& _group, int _t) : group(_group), t(_t) {}
bool operator() (int i, int j) {
return (group[i] == group[j])
? group[i+t] < group[j+t]
: group[i] < group[j];
}
};
vector<int> suffixArray(const string& s)
{
int n = s.size();
vector<int> ret(n), group(n+1), newGroup(n+1);
// 우선 앞에서부터 길이 1만큼만 정렬돼있음 (아스키코드값 그대로 넣기)
group[n] = -1;
for (int i = 0; i < n; ++i) group[i] = s[i];
for (int i = 0; i < n; ++i) ret[i] = i;
int t = 1;
while (true) {
Comp comp(group, t);
// 현재 앞에서부터 t만큼을 기준으로 정렬돼있고,
// 이정보를이용해 2t까지 정렬
sort(ret.begin(), ret.end(), comp);
t *= 2;
if (t >= n) break;
// 2*t까지 정렬한 정보를 갱신
newGroup[n] = -1;
newGroup[ret[0]] = 0;
for (int i = 1; i < n; ++i) {
if (comp(ret[i - 1], ret[i]))
newGroup[ret[i]] = newGroup[ret[i - 1]] + 1;
else
newGroup[ret[i]] = newGroup[ret[i - 1]];
}
swap(group, newGroup);
}
return ret;
}sparse array(희소배열?)의 성질과 비슷하다.
문자열을 비교하는데 상수시간이 걸리기 때문에 정렬은 nlogn.
그 정렬을 총 logn번 한다. (길이 1만큼, 2, 4,8만큼..)
문자열을 비교하는데 상수?
예를 들자면, 접미사들이 앞에서부터 길이 2만큼이 비교된 상태라고 하자(t=2)
그 정보를 활용해서 길이 4까지 비교한 결과를 도출해보자 (t=2*2)
group[a] group[b]가 다르면, 이미 앞에서 비교 완료됐으므로 바로 리턴.
만약 앞 두글자가 같다면 위 값이 같을 것이다. 그럼 group[a+2]와 group[b+2]를 비교하면 된다.
group[a+2]와 group[b+2]에는 a+2, b+2부터 2글자를 기준으로 비교한 값이 들어있기 때문이다.
이 값들을 활용해서 a부터, b부터 앞 4글자를 기준으로 정렬한 값을 구할 수 있다.
멘버마이어스 + 버킷정렬(계수정렬) O(nlogn)
대회준비 하시는 분만..
위 알고리즘에서 sort(ret.begin(), ret.end(), comp) 대신 계수정렬을 사용하는 알고리즘이다.
group (i, i+t)를 pair type stable sort 하면 된다. pair type stable sort 관련해서 따로 정리할 예정.
vector<int> suffixArray(const string& s)
{
int n = s.size(), m = max(256, n) + 1;
vector<int> ret(n), group(n+1), nextGroup(n+1), cnt(m), idx(n);
for (int i = 0; i < n; ++i)
ret[i] = i, group[i] = s[i];
int t = 1;
while (true) {
// 이번엔 람다로 구현
auto comp = [&](int i, int j) {
return (group[i] == group[j])
? (group[i + t] < group[j + t])
: (group[i] < group[j]);
};
// group[i+t]
for (int i = 0; i < m; ++i) cnt[i] = 0;
for (int i = 0; i < n; ++i) cnt[group[min(n, i+t)]]++;
for (int i = 1; i < m; ++i) cnt[i] += cnt[i - 1];
for (int i = n - 1; i >= 0; --i) idx[--cnt[group[min(n, i + t)]]] = i;
// group[i]
for (int i = 0; i < m; ++i) cnt[i] = 0;
for (int i = 0; i < n; ++i) cnt[group[i]]++;
for (int i = 1; i < m; ++i) cnt[i] += cnt[i - 1];
for (int i = n - 1; i >= 0; --i) ret[--cnt[group[idx[i]]]] = idx[i];
// 왜 1인지 이해한다면 성공
nextGroup[ret[0]] = 1;
for (int i = 1; i < n; ++i)
nextGroup[ret[i]] = nextGroup[ret[i - 1]] + comp(ret[i - 1], ret[i]);
t *= 2;
swap(group, nextGroup);
if (group[ret[n - 1]] == n) break;
}
return ret;
}LCP(Longest Common Prefix) 구현
브루트포스 O(N^2)
// 접미사배열 : sa
vector<int> commonPrefix(const string& s, const vector<int>& sa)
{
int n = sa.size();
vector<int> ret(n);
ret[0] = -1;
for (int i = 1; i < n; ++i) {
int k = 0;
int a = sa[i-1], b = sa[i];
while (k + a < n && b + k < n && s[a + k] == s[b + k])
k++;
ret[i] = k;
}
return ret;
}접미사배열 저장된 순서대로, 이전의 접미사와 비교했다. (i와 i-1비교)
참고로 일관성만 지킨다면 이후 접미사랑 비교해도 된다.
근데.. 접미사배열 만드는것보다 더 걸린다. 최적화할 수 없을까?
Kasai's algorithm O(N)
vector<int> commonPrefix(const string& s, const vector<int>& sa)
{
int n = sa.size();
// isa : sa의 역함수
vector<int> isa(n);
for (int i=0; i < n ; ++i) isa[sa[i]] = i;
vector<int> ret(n);
ret[0] = -1; // 이전과 비교해야하므로 정의되지 않음
for (int i=0, k=0; i < n ; ++i, k=max(k-1,0)) {
if ( isa[i]==0 ) continue; // 제일앞이라 비교대상 없음
int j = sa[isa[i]-1];
while (i+k<n && j+k<n && s[i+k]==s[j+k]) k++;
ret[isa[i]] = k;
}
return ret;
}k는 증가, 감소할 때 1만큼만 변한다.
k는 최대 n번 감소한다.
그리고 k는 n이하의 값을 유지한다.
따라서 k는 최대 O(n)만큼만 증가할 수 있다. (더 증가하고 싶어도, 한번에 증가할 수 있는 최대는 n이기 때문에 k가 다시 충분히 감소해야 다시 증가할 수 있다. 하지만 k는 최대 n만큼만 감소하기 때문에 ..)
-> O(n)
제일 긴 접미사부터 lcp를 구한다. 길이순대로 구하다보면, 다음에 구하는 접미사는 당연하게도 이전 접미사에서 맨 첫 글자를 제외한 접미사다. 여기서, 이전 접미사의 lcp가 k>0 이라고 했을 때, 그 다음접미사는 이전 접미사에서 한글자 뗀 것이므로 "최소" k-1이상의 commonPrefix 를 가짐이 보장된다. 따라서 0부터 비교할 필요가 없고 k번째글자부터 비교하면 된다.
Reference
