Move Fast

접미사 배열

• 접미사 배열이란 어떤 문자열의 접미사를 사전식 순서대로 나열한 배열을 말한다. 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;
}