(9248) Suffix Array

https://www.acmicpc.net/problem/9248

단계별로 풀어보기

60단계(문자열 알고리즘 2) 5번째

 

 

 

문자열 S가 있을 때 S의 i번째 인덱스부터 마지막 인덱스까지 포함된 부분문자열을 S의 접미사라고 한다. S 자체도 0번째 인덱스부터 시작되는 접미사이다. S의 모든 접미사를 사전 순으로 정렬한 것을 접미사 배열이라고 한다.

접미사 배열을 나이브하게 일반적인 정렬로 구현한다면 정렬에 O(N log N)이 걸리고, 두 문자열을 비교하는 것은 첫 인덱스의 문자부터 하나씩 비교해야 해서 O(N)이 걸리므로 총 O(N^2 log N)이 걸린다.

이를 O(N log^2 N)으로 최적화한 것이 맨버 마이어스 알고리즘이다. 만약 0~n-1까지의 모든 인덱스 i에서 시작하는 d글자 부분문자열 [i, i+d)의 집합 g_d가 정렬이 되어있다고 하자.이때 g_2d는 [i, i+2d) = [i+d)∪[i+d, i+2d)이므로 d글자 부분문자열의 pair 형태로 보면 각각의 부분문자열은 이미 g_d에서 정렬이 끝났으므로 정수의 pair 형태를 비교하는 것으로 바뀌어 두 원소를 O(1)만에 비교할 수 있다. 따라서 정렬에 O(N log N), 원소끼리 비교에 O(1)가 걸리고 d=1부터 n이상이 될 때까지 이 과정을 반복하므로 O(log N)번 반복해 총 O(N log^2 N)이 걸리게 된다. d=1에서 한 글자씩 정렬하는 것도 정수형인 char를 비교하는 것이므로 O(N log N) 안에 끝낼 수 있다.

여기서 char의 범위가 매우 작다는 것을 생각하면 시간을 더 줄일 수도 있는데, 카운팅 정렬을 이용하는 것이다. d=1에서는 바로 할 수 있고, d에서 2d로 넘어갈 때 앞쪽, 뒤쪽을 기준으로 카운팅 정렬을 두 번 해주면 된다. 단, 두 번째 정렬은 안정된 정렬이여야 한다. 일반적인 정렬 O(N log N)에 비해 카운팅 정렬은 O(N)이 걸리므로 접미사 배열을 O(N log N)에 구할 수 있다.

 

하지만 이것만으로 풀 수 있는 문제는 별로 없고, LCP배열을 추가로 구해야 한다. LCP는 Longest Common Prefix의 약자로 LCP[i]는 접미사 배열의 i-1번째 부분문자열과 i번째 부분문자열에서 겹치는 가장 긴 접두사의 길이이다(접미사 배열에서 인접한 원소끼리의 LCP만 구하면 모든 LCP를 구할 수 있다고 한다).

LCP배열은 카사이 알고리즘을 이용해 O(N)으로 구할 수 있는데, 원본 문자열의 인덱스 순서대로 LCP를 구한다. 원본 문자열의 i번째 인덱스에서 앞쪽 접미사 배열 원소의 j번째 인덱스와 비교해 구한 LCP값이 x라면, 원본 문자열의 i+1번째 인덱스를 앞쪽 접미사 배열 원소와 비교할 때 x-1글자가 같다는 것이 보장된다. 따라서 LCP를 처음부터 비교하지 않고 x-1번째부터 비교하여 시간을 줄일 수 있다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  string s;

  cin >> s;

  int n= s.length(), d= 1, n2= max(27, n+1);
  vector<int> sfx(n), cnt(n2), idx(n), g(n), tg(n), lcp(n);

  for(int i=0;i<n;i++){
    sfx[i]= i;
    g[i]= s[i]-'a'+1;
  }
  
  while(1){
    fill_n(cnt.begin(), n2, 0);
    for(int i=0;i<n;i++)  cnt[i+d<n?g[i+d]:0]++;
    for(int i=1;i<n2;i++)  cnt[i]+= cnt[i-1];
    for(int i=n-1;i>=0;i--)  idx[--cnt[i+d<n?g[i+d]:0]]= i;
    
    fill_n(cnt.begin(), n2, 0);
    for(int i=0;i<n;i++)  cnt[g[i]]++;
    for(int i=1;i<n2;i++)  cnt[i]+= cnt[i-1];
    for(int i=n-1;i>=0;i--)  sfx[--cnt[g[idx[i]]]]= idx[i];

    tg[sfx[0]]= 1;
    for(int i=1;i<n;i++){
      int curr= sfx[i], prev= sfx[i-1];
      
      bool same= g[curr]==g[prev] && ((curr+d<n?g[curr+d]:0) == (prev+d<n?g[prev+d]:0));
      
      tg[curr]= tg[prev]+!same;
    }

    g= tg;

    if(g[sfx[n-1]]==n)  break;
    d<<= 1;
  }

  s+= ' ';
  
  for(int i=0,k=0;i<n;i++){
    if(g[i]-1){
      int j= sfx[g[i]-2];

      while(s[j+k]==s[i+k])  k++;

      lcp[g[i]-1]= k;
      k= max(k-1,0);
    }
  }

  for(int i=0;i<n;i++)  cout << sfx[i]+1 << " ";
  cout << "\nx ";
  for(int i=1;i<n;i++)  cout << lcp[i] << " ";
  
  return 0;
}