접미사 배열(Suffix Array)과 최장 공통 접두사 배열(LCP Array)

r4v3n-k 2021. 1. 28. 14:15

2021. 1. 28. 14:15

접미사 배열

접미사 배열이란 어떤 문자열의 접미사를 사전식 순서대로 나열한 배열을 말한다. by Wikipedia
문자열 "banana" 의 접미사는 다음과 같다.

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

Move Fast

접미사 배열(Suffix Array)과 최장 공통 접두사 배열(LCP Array)

접미사 배열

Naive Method

Manber-Myers Algorithm

최장 공통 접두사 배열

'Algorithm > Theory' 카테고리의 다른 글

+ Recent posts

티스토리툴바