Suffix Array, LCP Array

Suffix Array

---

접미사 배열(suffix array)는 어떤 문자열 S의 모든 접미사를 사전순으로 정렬해둔 것으로, 보통 각 접미사의 시작 위치를 저장하는 정수 배열로 구현된다. 길이가 \(n\)인 문자열의 접미사 배열을 만드는 가장 빠른 알고리즘은 \(O(N)\)만에 접미사 배열을 만든다고 한다. 하지만 프로그래밍 대회에서는 이 복잡한 알고리즘을 직접 구현하여 사용하기에는 어려워 보통 그 대안으로 적당히 구현하기 쉽고, 적당히 빠른 알고리즘을 대신 사용한다.

접미사 배열을 만드는 \(O(N{log_2}^2N)\) 알고리즘은 각 접미사를 첫 한 글자로 정렬하고, 그 다음에 두 글자, 네 글자.. 로 \(log_2N\) 번 정렬하는 것이다. 각 접미사들이 서로 완전히 다른 문자열들이 아니라 두 접미사중 하나가 다른 하나를 포함하고 있기 때문에 이전 정렬에서 얻은 정보를 이용해서 두 접미사의 대소 비교를 \(O(1)\)에 수행한다.

구현

접미사 배열을 만드는 \(O(N{log_2}^2N)\) 알고리즘은 다음과 같이 구현할 수 있다.

// 각 접미사들의 첫 t글자를 기준으로 한 group 번호가 주어질 때, // 주어진 두 접미사를 첫 2*t 글자를 기준으로 비교한다. // (group 번호가 낮을 수록 t 글자를 기준으로 앞에 있다. t 글자가 같을 경우 group 번호는 같다.) struct Comparator { const vector<int>& group; const int t; Comparator(const vector<int>& _group, const int _t) : group(_group), t(_t) { } bool operator() (const int l, const int r) { if (group[l] != group[r]) return group[l] < group[r]; return group[l + t] < group[r + t]; } }; // str의 접미사 배열을 생성한다. vector<int> getSuffixArray(const string& str) { int n = str.length(); vector<int> ret(n); vector<int> group(n + 1); for (int i = 0; i < n; i++) { ret[i] = i; group[i] = str[i]; } group[n] = -1; // 각 접미사를 첫 1, 2, 4, 8, ... 글자를 기준으로 정렬해나간다. int t = 1; while (t < n) { Comparator comparator(group, t); sort(ret.begin(), ret.end(), comparator); t *= 2; if (t >= n) break; vector<int> newGroup(n + 1); newGroup[n] = -1; newGroup[ret[0]] = 0; for (int i = 1; i < n; i++) { if (comparator(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; }

위의 알고리즘에서는 정렬 시에 보통의 \(O(Nlog_2N)\) 알고리즘을 사용하지만, 선형 시간복잡도를 가지는 계수 정렬(Counting Sort)를 이용하면, 아래와 같이 접미사 배열을 만드는 총 시간복잡도를 \(O(Nlog_2N)\)로 줄일 수 있다.  

// 첫 k 글자를 기준으로 매겨진 group 번호를 이용하여 접미사 배열을 계수 정렬한다. void countingSort(int k, vector<int>& perm, vector<int>& group) { int n = perm.size(); // 계수 정렬시 사용하는 bucket의 범위 // 첫 group 번호는 문자의 아스키 코드를 이용하므로 char의 최댓값을 담을 수 있어야 하고, // 그 이후에는 0번부터 최대 n-1까지 매겨질 수 있으므로 이에 맞게 range를 잡는다. int range = max(n, (int)numeric_limits<char>::max()); vector<int> cnt(range + 1, 0); for (int i = 0; i < n; i++) { if (i + k < n) cnt[group[i + k]]++; else cnt[0]++; } for (int i = 1; i <= range; i++) { cnt[i] += cnt[i - 1]; } vector<int> newPerm(n); for (int i = n - 1; i >= 0; i--) { if (perm[i] + k < n) newPerm[--cnt[group[perm[i] + k]]] = perm[i]; else newPerm[--cnt[0]] = perm[i]; } swap(perm, newPerm); } // 문자열 s의 접미사 배열을 반환한다. vector<int> getSuffixArray(const string& s) { int n = s.size(); // 접미사 배열, 각 접미사의 시작 위치를 저장하는 순열로 볼 수 있다. vector<int> perm(n); for (int i = 0; i < n; i++) { perm[i] = i; } // 각 접미사들의 첫 k 글자를 기준으로 매겨진 group 번호 // 첫 k 글자가 사전상 앞에 있을 수록 상대적으로 낮은 번호를 부여한다. vector<int> group(n + 1); for (int i = 0; i < n; i++) { group[i] = s[i]; } // 각 접미사를 첫 2, 4, 8, ... 글자를 기준으로 O(lg n)번 정렬한다. for (int k = 1; k < n; k *= 2) { countingSort(k, perm, group); // 첫 [k ~ 2*k) 글자를 기준으로 정렬 countingSort(0, perm, group); // 첫 [0 ~ k) 글자를 기준으로 정렬 // group 번호를 갱신한다. vector<int> newGroup(n + 1); // 새 group 번호 (임시 배열) newGroup[perm[0]] = 0; for (int i = 1; i < n; i++) { if (group[perm[i]] == group[perm[i - 1]] && group[perm[i] + k] == group[perm[i - 1] + k]) newGroup[perm[i]] = newGroup[perm[i - 1]]; else newGroup[perm[i]] = newGroup[perm[i - 1]] + 1; } swap(group, newGroup); if (group[perm[n - 1]] == n - 1) break; // 최적화 } return perm; }

Longest Common Prefix Array

---

접미사 배열과 함께 자주 사용되는 것이 있는데 바로 LCP 배열이다. Longest Common Prefix, 말 그대로 가장 긴 공통 접두사를 의미하는데, 여기서 말하는 LCP 배열은 (사전순으로 정렬되어 있는) 접미사 배열에서 이전 접미사와의 최장 공통 접두사의 길이를 저장한다. 문자열, 그 문자열의 접미사 배열, 그리고 LCP 배열의 관계는 아래 표를 보면 이해하기가 쉽다.

i	suffixArray[ i ]	suffix	LCP[ i ]
0	5	a
1	3	ana	1
2	1	anana	3
3	0	banana	0
4	4	na	0
5	2	nana	2

LCP 배열은 접미사 배열에서 사전상으로 인접한 두 접미사의 최장 공통 접두사의 길이를 하나 하나 세면 되지만, 이 방식은 \(O(N^2)\)의 시간이 소요되는 방식이다. 이 LCP 배열을 계산하는 보다 효율적인 \(O(N)\) 알고리즘이 존재하는데 그 핵심 아이디어는 접미사 배열을 계산할 때와 마찬가지로 한 접미사는 다른 접미사의 접미사라는 점을 이용하여 중복된 계산을 줄이는 것이다.

i	suffixArray[ i ]	suffix	LCP[ i ]
0	5	a
1	3	ana	1
2	1	anana	3
3	0	banana	0
4	4	na	0
5	2	nana	2

위의 접미사 배열에서 인접한 접미사 "ana"와 "anana"의 LCP는 3이라는 것을 계산했다고 하자. 그 후에 "na", "nana"의 LCP를 계산하려고 할 때, 한 가지 사실을 알 수 있다. 이미 "ana"와 "anana"의 LCP는 3이라고 계산해두었기 때문에 앞의 a가 없는 "na"와 "nana"의 LCP는 최소 2라는 사실이다. (보다 자세한 내용은 여기를 참고하면 될 것 같다.)

즉, S[i..], 그리고 S[i..]와 사전상으로 인접한 접미사(접미사 배열상 바로 이전 접미사)와의 LCP를 \(m\)이라고 하면, S[i+1..], S[i+1..]와 사전상으로 인접한 접미사의 LCP는 최소 \(m-1\) 이므로 이 부분은 중복하여 계산하지 않아도 된다.

구현

// 문자열 s와 s의 접미사 배열이 주어졌을때, LCP 배열을 생성한다. vector<int> getLCPArray(const string& s, vector<int>& suffixArray) { int n = s.length(); vector<int> lcp(n); // rank[i]: s[i..]가 사전상 몇 번째 접미사인지를 나타낸다. vector<int> rank(n); for (int i = 0; i < n; i++) rank[suffixArray[i]] = i; int matched = 0; for (int i = 0; i < n; i++) { int k = rank[i]; if (k) { int j = suffixArray[k - 1]; while (s[j + matched] == s[i + matched]) ++matched; lcp[k] = matched; if (matched) --matched; } } return lcp; }

예제

• BOJ 9248 Suffix Array
  
• BOJ 11478 서로 다른 부분 문자열의 개수

참고 자료

• JMBOOK, 구종만
  
• Competitive Programming 3, Steven Halim & Felix Halim
• http://jason9319.tistory.com/141
• http://blog.naver.com/dark__nebula/220419358547