접미사 배열

길이 N인 문자열의 접미사 N개를 사전 순으로 정렬해 놓은 배열을 접미사 배열이라고 한다. 접미사 배열에 문자열을 저장하면 메모리가 $\BigO{N^2}$만큼 필요한데 이는 심각한 낭비이다. N개의 접미사에 시작 위치를 기준으로 0부터 N-1까지 번호를 붙일 수 있으므로 이 번호를 저장하자. 그러면 접미사 배열을 $\BigO{N}$의 메모리로 나타낼 수 있다.

접미사 배열은 중복되는 부분문자열을 찾기에 유용하다. "mississipi"라는 문자열에서는 "issi"가 두 번 반복된다. "issi"처럼 부분문자열이면서 중복되는 문자열들을 찾고 싶으면 어떻게 하면 될까?

접미사 배열이 사전순으로 정렬되어 있다는 것을 이용해보자. 일단 부분문자열들은 모두 어떤 접미사의 접두사일 것이다. 접미사 배열에서 앞부분들을 보자.

접미사 배열에서 2번과 3번에 "issipi"와 "ississipi"가 들어있다. "issi"는 중복되기 때문에 접미사 배열의 여러 곳에서 접미사들의 접두사로 나타남을 볼 수 있다. 하지만 접미사 배열은 사전 순으로 정렬되어 있으므로 중복되는 문자열들은 산발적으로 분포하는 것이 아니라 항상 서로 이웃해 있다. 이를 이용하여 이웃한 접미사들의 공통 접두사를 확인하면 공통부분문자열을 확인할 수 있다.

Manber-Myers Algorithm

접미사 배열을 어떻게 구할까? 가장 쉬운 방법은 그냥 std::sort 함수를 쓰는 것인데 숫자를 정렬할 때와 다르게 문자열을 비교할 때는 문자열의 길이만큼 시간이 걸리기 때문에 $\BigO{N^2\log{N}}$의 시간이 걸리게 된다. 이를 빠르게 해결할 수 있는 알고리즘으로 맨버-마이어스 알고리즘이 있다. 이 알고리즘의 핵심은 접미사들을 앞에서 \(x\)만큼만 봤을 때 정렬해 놓은 결과를 이용해서 \(2x\)만큼 봤을 때의 정렬을 빠르게 수행하는 것이다. 다음 표를 보면서 확인해 보자.

이는 "tetetetell"의 접미사들을 맨버-마이어스 알고리즘을 통해 정렬하는 과정을 나타낸 것이다. 처음에는 1글자만 비교해서 정렬한다. 첫 글자가 e,l,t인 것들끼리는 정렬이 되지 않은 것을 볼 수 있다. 2글자까지 보고 비교할 때는 1글자를 비교해 놓은 것을 이용해서 정렬한다. S[x\(\cdots\)] 와 S[y\(\cdots\)]를 비교하는데 첫 글자가 다르면 쉽게 비교가 가능하지만 만약 같다면 어떻게 할까? 바로 S[x+1 \(\cdots\)] 와 S[y+1\(\cdots\)]를 통해 비교하는 것이다. 만약 S[x+1\(\cdots\)]와 S[y+1\(\cdots\)]도 첫글자가 같다면 2글자가 같은것이므로 지금 정렬하지 않아도 된다. 마찬가지로 \(2^{i+1}\)글자까지 비교하고 싶다면 S[x\(\cdots\)]와 S[y\(\cdots\)]를 비교할 때는 S[x\(\cdots\)]와 S[y\(\cdots\)]를 \(2^i\)까지 정렬해 놓은 결과와 S[x+\(2^i\cdots\)]와 S[y+\(2^i\cdots\)]를 \(2^i\)까지 정렬해 놓은 결과를 가지고 비교할 수 있다.

char a[MAX_N]; int s[MAX_N], grp[MAX_N], grp2[MAX_N], sz; bool cmp(int x,int y){ return grp[x]!=grp[y] ? grp[x]<grp[y] : grp[x+sz]<grp[y+sz]; } void new_grp(){ grp2[s[0]] = 0; for (int i=1; i<N; i++) { grp2[s[i]] = grp2[s[i-1]]; if (cmp(s[i-1],s[i])) grp2[s[i]]++; } swap(grp,grp2); } void suffixArray() { for (int i=0; i<N; i++) { s[i] = i; grp[i] = a[i]; } grp[N] = grp2[N] = -1; sort(s, s+N, cmp); new_grp(); for (sz=1; sz<N; sz<<=1) { sort(s, s+N, cmp); grp2[s[0]] = 0; for (int i=1; i<N; i++) { grp2[s[i]] = grp2[s[i-1]]; if (cmp(s[i-1], s[i])) grp2[s[i]]++; } for (int i=0; i<N; i++) { grp[i] = grp2[i]; } } }
맨 처음에 접미사의 처음 시작하는 문자를 가지고 비교한 후 그룹을 묶고 다음부터는 비교하는 길이를 2배씩 늘려가면서 정렬을 시킨다.

이 알고리즘은 비교하는 글자 수를 2배씩 증가시켜서 총 \(\log{N}\)번 도는 반복문 안에서 $\BigO{N\log{N}}$인 std::sort를 시행하므로 $\BigO{N\log^{2}{N}}$의 시간복잡도를 가진다.

반복문 안에서 std::sort 함수를 쓰지 않고 $\BigO{N}$의 카운팅 소트를 실시함으로써 시간복잡도를 $\BigO{N\log{N}}$으로 줄일 수 있다.
void suffixArray() { for (int i=0; i<N; i++) { s[i] = i; grp[i] = a[i]; } grp[N] = grp2[N] = -1; sort(s, s+N, cmp); new_grp(); for (sz=1; sz<N; sz<<=1) { int pos = 0; for (int i=N-sz; i<N; i++) grp2[pos++] = i; for (int i=0; i<N; i++) if (s[i]>=sz) grp2[pos++] = s[i]-sz; memset(cnt, 0, sizeof(cnt)); for (int i=0; i<N; i++) cnt[grp[grp2[i]]]++; for (int i=1; i<N; i++) cnt[i] += cnt[i-1]; for (int i=N-1; i>=0; i--) s[--cnt[grp[grp2[i]]]] = grp2[i]; new_grp(); } }

이 코드는 myungwoo님의 코드를 참고했다. http://blog.myungwoo.kr/57

맨 처음에 처음 문자를 가지고 정렬할 때에도 $\BigO{N}$에 카운팅 소트를 할 수도 있지만, 문자열에 소문자와 대문자가 같이 있는 경우나 특수문자가 포함되는 경우에는 골치 아파지기 때문에 std::sort를 사용하였다.

반복문 내에서 grp2에 들어가는 값들을 살펴보면 같은 그룹에 속한 접미사들이 2sz만큼 비교한 값들로 정렬되어 있음을 알 수 있다. 그 후에 각 그룹에 들어있는 원소 개수를 세서 접미사 배열에 채워 넣는 것을 모두 $\BigO{N}$에 처리할 수 있다.

Baekjoon Online Judge에 있는 접미사 배열 문제에 두 알고리즘을 다 내보았는데 $\BigO{N\log{N}}$코드가 2배 정도밖에 안 빠르고 $\BigO{N\log^{2}{N}}$코드도 시간 내에 잘 돌아가서 개인적으로는 코드가 더 간결한 $\BigO{N\log^{2}{N}}$코드를 선호한다.

Longest Common Prefix
Longest Common Prefix(lcp)는 두 접미사의 최대 공통 접두사의 길이를 말한다. 접미사 배열에서 lcp는 중요한 의미를 가진다. 중복된 부분 문자열은 접미사 배열에서 이웃해 있으므로 lcp를 구할 수 있다면 중복된 부분 문자열의 최대 길이를 구할 수 있다.

lcp를 구할 때는 접미사 배열에서 이웃한 두 접미사의 lcp만 구하면 충분하다. 서로 떨어진 접미사의 lcp는 구간 내에 있는 lcp들의 최솟값이기 때문에 세그먼트 트리 등의 자료구조를 사용하여 계산할 수 있기 때문이다.

접미사 배열에서 i-1번째 접미사와 i번째 접미사 사이의 lcp를 l[i]로 하는 lcp 배열 l을 생각해 보자. l[i]를 구하는 간단한 방법은 접미사 배열에서 i-1번째 접미사와 i번째 접미사를 처음부터 비교하면서 처음으로 불일치 하는 곳을 찾는 것이다. 이러면 l[1]부터 l[N-1]까지 모두 구하는데 $\BigO{N^2}$의 시간이 걸릴 것이다. 이것을 $\BigO{N}$에 해결하는 방법이 있다.

접미사 배열 s[i]의 역함수 rs[i]를 정의하자. rs[i]는 S[i\(\cdots\)]가 s에서 몇 번째에 있는지를 알려주는 배열이다. 여기서 재미있는 사실이 있는데 l[rs[i-1]]-1\(\leq\)l[rs[i]]을 만족한다는 것이다. 다음 그림을 보면 이해를 쉽게 할 수 있을 것이다.

S[i-1\(\cdots\)]가 접미사 배열에서 바로 위에 있는 접미사 S[x\(\cdots\)]와 $y$만큼 앞부분이 일치한다고 하자. 이제 l[rs[i-1]] = $y$ 일때, l[rs[i]] $\geq y-1$ 임을 보일 것이다.

 

먼저, $y\leq 1$ 이면, l[rs[i]] $\geq 0$ 이 되므로, 자명하다. 따라서, $y\geq 2$라고 가정하자.

 

S[i\(\cdots\)]는 S[x+1\(\cdots\)]과 $y-1$만큼 앞부분이 일치할 수밖에 없다. 사전 순으로 S[x\(\cdots\)]가 S[i-1\(\cdots\)]보다 앞에 왔으므로 S[x+1\(\cdots\)]도 S[i\(\cdots\)]보다 앞에 올 수밖에 없다. S[x+1\(\cdots\)]가 S[i\(\cdots\)]바로 위에 있지 않더라고 해도 S[x+1\(\cdots\)]와 S[i\(\cdots\)]사이에 있는 접미사들은 사전 순으로 정렬되었다는 조건에 의해 앞부분의 $y-1$개의 문자가 반드시 일치해야만 한다. 따라서 S[i\(\cdots\)]는 lcp가 $y-1$ 이상임이 보장된다.

 

 

이 사실을 이용하면 다음과 같이 간단하게 lcp를 구할 수 있다.

void lcp() { for (int i=0; i<N; i++) rs[s[i]] = i; int h = 0; for (int i=0; i<N; i++) { if (rs[i]== 0) continue; while (a[i+h] == a[s[rs[i]-1]+h]) h++; l[rs[i]] = h; if (h>0) h--; } }

while문에서 h가 증가하는데 문자열의 길이 N보다는 커질 수가 없다. 또, for문을 돌면서 h가 최대 N번 감소할 수 있다. 따라서, h는 최대 2N번 증가할 수 있고 시간복잡도가 $\BigO{N}$이 된다.

UPDATE

2021-11-19 lcp 증명 내용 수정