[알고리즘 소개] String algorithm - Suffix Array

Suffix Array란 무엇인고?

항상 String 관련 알고리즘에 자주 등장하는 바나나의 예시를 들어보자.

 

S = "banana"

 

Suffix라고 함은 접미사라는 뜻인데, 끝에서부터 한 글자, 끝에서부터 두 글자 이렇게 해서 전체 글자까지 나타낼 수 있다.

a - 5 na - 4 ana - 3 nana - 2 anana - 1 banana - 0

 

이 친구들을 사전순으로 정렬하면

a - 5 ana - 3 anana - 1 banana - 0 na - 4 nana - 2

가 된다.

이 때, [5,3,1,0,4,2]를 저장한 Array를 Suffix Array라고 한다.

 

어떻게 구현해?

당연히, 조금만 생각하면 O(N^2 logN) (Naive Sort), O(N^2) (Trie) 정도는 바로 생각해낼 수 있다. 하지만 이정도로는 대회에서 쓰일 정도로는 많이 부족하다. 여기서 소개할 알고리즘은 O(NlogNlogN), O(NlogN)이다.

 

맨버-마이어스 알고리즘(Manber-Myers Algorithm)

조금 복잡한 알고리즘이기에 각 배열, 변수가 의미하는 바를 정확히 짚고 가자.

S[0..N-1] : 원래 문자열(위의 예제에서 “banana”)
G[i] : 접미사 S[i..N-1]의 Grade(순위).
          위의 banana 예시에서 최종적으로 G[5]=0, G[3]=1, G[1]=2가 되어야 할 것이다.
tG[i] : G[i] 갱신을 위한 배열, temporary Grade
t : G[i]의 갱신을 위해 1부터 2배씩 증가하는 파라미터.
SA[i] : 위에서 소개한 Suffix Array

 

① Overview

핵심 아이디어는 G[i]를 갱신하는 방법이다. 

이 때 G[i]는 i번째 문자부터 1개의 문자, 2개의 문자, ..., t(=2^k)개의 문자에 대한 Grade이며,

이를 갱신할 때 G[i]를 (G[i], G[i+t]) 순으로 다시 재정렬하는 것이 핵심이다.

말로 설명하기 어려워 최대한 표로 직관적으로 설명해보려고 노력하였다.

i	0	1	2	3	4	5
S[i]	b	a	n	a	n	a
G[i]가 고려하는 대상	‘b’	‘a’	‘n’	‘a’	‘n’	‘a’
G[i]	2	1	14	1	14	1
(G[i], G[i+t])	(2,1) => ‘ba’	(1,14) => ‘an’	(14,1) => ‘na’	(1,14) => ‘an’	(14,1) => ‘na’	(1,-) => ‘a’
새로 갱신될 G[i]	3	2	4	2	4	1

<초기값 및 첫 번째 반복, t=1>

 

i	0	1	2	3	4	5
S[i]	b	a	n	a	n	a
G[i]가 고려하는 대상	'ba'	'an'	'na'	'an'	'na'	'a'
G[i]	3	2	4	2	4	1
(G[i], G[i+t])	(3,4) = ((2,1), (14,1)) => bana	(2,2) = ((1,14),(1,14)) => anan	(4,4) = ((14,1),(14,1)) => nana	(2,1) = ((1,14),(1,-)) => ana	(4,-) = ((14,1), -) => na	(1,-) = ((1,-) , -) => a
새로 갱신될 G[i]	4	3	6	2	5	1

<두 번째 반복, t=2>

 

i	0	1	2	3	4	5
S[i]	b	a	n	a	n	a
G[i]가 고려하는 대상	‘bana’	‘anan’	‘nana’	‘ana’	‘na’	‘a’
G[i]	4	3	6	2	5	1
(G[i], G[i+t])	(4, 5) = ((3,4), (4,-))	(3, 1) = ((2,2),(1,-))	(6,-) = ((4,4), -)	(2,-) = ((2,1), -)	(5,-) = ((4,-), -)	(1,-) = ((1,-), -)
새로 갱신될 G[i]	4	3	6	2	5	1

<세 번째 반복, t=4>

 

G[i]를 모두 갱신하였을 경우 SA[i]는 G[SA[i]]로 정렬하면 되기 때문에 G[i]를 구하는 것이 가장 큰 문제이다.

 

② 소스 코드 및 설명

3~8 : comp 함수 정의. a, b에 대해서 (G[a], G[a+t])와 (G[b], G[b+t])를 비교한다.

12~15 : 초기화 단계. G[i]를 S[i], 즉 아스키 코드 값으로 초기화해준다.
(만약 문제가 대문자 or 소문자만으로 이루어져 있다고 한다면 S[i]-'A', S[i]-'a'와 같이 해주어도 무방하다)

18 : SA를 (G[SA[i]], G[SA[i]+t])가 작은 순서대로 정렬한다. 즉, 새로 갱신될 G[i]의 index 순서대로 정렬해준다.
Suffix Array를 바로 구한다기보다, G[i]를 새로 갱신하기 위해 정렬한다고 생각하면 편하다.

19 : G(SA[i], G[SA[i]+t]) 값이 가장 작은 i(=0)의 grade를 새로 0으로 지정한다.

20~25 : 1부터 N-1까지 (G[SA[i]], G[SA[i]+t])가 (G[SA[i-1]], G[SA[i-1]+t])와 똑같은 경우 i-1와 똑같은 값을, 더 큰 경우 i-1보다 1 큰 값을 tG[SA[i]]에 넣는다.
18 line에서 (G[SA[i-1]], G[SA[i-1]+t]) <= (G[SA[i]], G[SA[i]+t])임이 보장된다(정렬을 했으므로)

26 : G에 새로 구한 Grade, tG를 넣는다.

27 : t를 2배 증가한다(Grade를 매기는 S의 범위가 두 배 증가한다)

 

내 머리가 빡대가리인건지 모르겠지만 10개 정도 관련문제를 풀고 그 때마다 하나하나 다 따져보고 이해가 안 되는 것들이 있다면 다시 찾아보고 해서 이해가 갔던 기억이 난다.

 

위 소스의 경우 루프가 logN번 실행되며 루프 내에 sort()함수가 있어 전체 시간복잡도는 O(N(logN)^2) 이다.

 

③ O(NlogN)으로 줄이는 방법

크게 어려울 것 없이 sort() 함수를 카운팅 소트로 바꾸어서 해결할 수 있다. G의 범위가 max(문자 종류 개수, N)이기 때문에 사실상 N이고, 따라서 카운팅 소트로 해결하면 원만히 해결된다.

다만, 일반적인 정렬이 아니라 pair의 정렬이기 때문에 조금의 노력이 필요하다. 이는 다음 포스트에서 다루도록 하겠다.

 

 

굉장히 쓸데없어 보이고 실제로 이 알고리즘 자체만 쓰는 문제는 많지 않다만, suffix array를 활용한 문제들이 큰 대회에서 꾸준히 출제되고 있고(scpc 5회, 7회 본선문제 등등) lcp array 또한 활용도가 높기 때문에 어느정도 수준이 있는 대회에 참가할 때 익히는 것이 좋다고 생각한다.