Suffix Array (접미사 배열)

다음과 같은 참고 자료들이 있으니 같이 보자.

http://web.stanford.edu/class/cs97si/suffix-array.pdf

http://web.stanford.edu/class/cs97si/10-string-algorithms.pdf

http://blog.myungwoo.kr/57

http://m.blog.naver.com/dark\_\_nebula/220419358547

Suffix Array는 문자열과 부분문자열을 가지고 놀 수 있는 자료구조이다. 이름만 보면 도대체 어디에 쓰는 것인지 잘 이해도 안 가고 왜 배우는 지도 알 수 없을 것이다. 일단, Suffix Array를 통해서 쉽게 풀 수 있는 문제 몇가지를 나열하자면 :

* 길이 |S|의 스트링 하나와, Q개의 길이 Ti의 스트링이 주어진다. O(Sum(|T|)) 즈음의 시간에 주어진 Q개의 스트링이 부분문자열인지 판별할 수 있는가? ( KMP 알고리즘으로는 O(|S|*Q)의 시간이 걸린다 )

* 문자열 |S|의 위치 p1, p2가 있을 때, [p1, p1 + l - 1] == [p2, p2 + l - 1]을 만족하는 가장 긴 l을 쿼리당 빠르게 구할 수 있는가? (Longest common prefix라고도 불리는 문제이다)

Suffix Array로 풀리는 굉장히 유명한 문제들은 대충 이렇다. 보통 주어진 긴 문자열의 부분문자열과 관련된 문제에서 매우 유용하게 사용되는 자료구조이다.

먼저, Suffix Trie라는 자료구조를 소개하려고 한다. Suffix Trie는 문자열 S에 대해서, S의 접미사들을 모두 넣고 만든 trie이다. 시간 복잡도와 공간 복잡도는 대략 O(N^2) 정도이다. 이러한 자료구조가 만들어져 있다면, 위 두 문제는 다음과 같이 해결할 수 있다.

* 1번 문제는 단순한 trie 순회로 해결 가능하다. 즉, O(Sum(|T|))

* 2번 문제는, [p1, |S| - 1] suffix와 [p2, |S| - 1] suffix로 만들어 낸 path가 얼마나 겹치는지를 계산함으로써 풀 수 있다. 이 때, 이 과정이 트리의 LCA를 구하는 과정과 똑같다는 것을 알면, 시간 복잡도를 향상시킬 수 있다. (O(lgN))

애석하게도, Suffix Trie는 O(N^2)에서 시간 복잡도를 향상시키기 쉽지 않다. Suffix Tree라는, O(N)짜리 Suffix Trie의 변형이 있기는 한데 매우 복잡하니 그냥 모른척 해주자. 우리가 배울 Suffix Array는 Suffix Trie의 강력한 부분문자열 검색 능력을, O(N) 메모리와 O(NlgN) 시간 복잡도에 해주는 꿀같은 자료구조이다. (사실 Suffix Array도 O(N)에 계산 가능하지만 꽤 복잡하니 모른척 해주자...)

문자열 |S|의 Suffix Array sfx[]는, 모든 sfx[i]에 대해서, 사전순으로 (i+1)번째인 suffix가 S[sfx[i], N-1] 를 만족하는 자료구조이다. 이렇게 얘기하면 무슨 말인지 알기 쉽지 않지만, 쉽게 말해서 모든 suffix를 정렬했다고 생각하면 된다.

S = "banana" 일때, S의 suffix는 {"banana", "anana", "nana", "ana", "na", "a"} 이다. 이걸 토대로 suffix array를 만들면

sfx[0] = 5 ("a")

sfx[1] = 3 ("ana")

sfx[2] = 1 ("anana")

sfx[3] = 0 ("banana")

sfx[4] = 4 ("na")

sfx[5] = 2 ("nana")

sfx[i]에는, 각각의 부분 문자열의 시작 위치가 저장되어 있고, 이 suffix array를 따라 suffix를 찍어보면 모두 사전순 정렬되어 있다는 것을 알 수 있다. 이제 이러한 자료구조를 어떻게 O(NlgN)에 만드는 지가 관건이다.

Naive한 O(N^2lgN) 방법은, cmp 함수를 O(N)에 작동하게 한 후 단순히 sort를 함으로써 가능하다. 이를 O(NlgN)으로 줄이려면, 길이 K인 suffix를 정렬한 suffix array에서, 길이 2K인 suffix를 정렬한 suffix array를 O(N)에 유도할 수 있다는 것을 이해해야 한다. 길이를 2^K >= N까지 늘리면 suffix array를 만들 수 있으니, O(N)에 유도할 수 있으면 O(NlgN)에 해결할 수 있다.

먼저, O(NlgN)에 유도하는 법에 대해서 생각해보자. ord[i] = i에서 시작하는 suffix array의 순위라고 생각해보자. 순위라는 말이 참 애매하지만, 대충 "정렬 기준" 이라고 생각하면 편하겠다. 목표는, ord[sfx[i]] = i를 만족할 때까지, ord 배열을 계속 조정하는 것이다.

처음 ord[i] = str[i] 로 잡자. 즉, 각각의 suffix의 첫 글자를 기준으로 정렬 기준을 설정하는 것이다. 만약에 suffix의 첫 글자가 다르다면 순서가 맞겠지만 아닐 때는 순서를 구분할 수 없을 것이다. 이를 위해서, [0 ~ N-1] 까지의 숫자가 담긴 배열을 다음과 같은 정렬 함수로 정렬하자.

ord[i] != ord[j]라면 ord[i] < ord[j] 순으로 정렬한다. 아닐 경우, ord[i+1] < ord[j+1] 순으로 정렬한다. 만약, ord[x]를 접근할 때 x >= |S|일 경우, ord[i] = -inf.

이렇게 suffix array를 만들었다면, suffix의 두 글자 까지는 순서를 구분할 수 있게 된다. 현재의 suffix array를 순서대로 순회하는데, ord[i] == ord[j] 이면서 ord[i+1] == ord[j+1] 일 경우 order 값을 같은 값을 주고, 아닐 경우 순서대로 증가하는 형태로 새로운 order를 주면 되기 때문이다. ( [0, 0, 0, 0, 1, 1, 2, 3, 4, 5.. ] 이런 느낌. ) 이제 1 -> 2 -> 4 -> 8로 이 값을 충분히 늘려나가면 O(Nlg^2N)에 문제를 해결할 수 있다. (https://gist.github.com/koosaga/44532e5dec947132ee55da0458255e05 코드의 33 - 42줄이 이러한 내용을 구현했다.)

이를 O(N)으로 줄이는 것이 관건인데, 이는 counting sort로 해결 가능하다. ord[i]의 값이 counting sort로 해결할 수 있는 범위이니, 위의 정렬을 O(N)에 해결하면 되는 것이다. 다만 두개의 인자를 봐야 하는 것이 문제인데, 아무 수열이나 잡고 ord[i+p]를 기준으로 counting sort를 먼저 해 둔 후, ord[i+p] 가 증가하는 순으로 보면서 ord[i]를 기준으로 또 counting sort를 하면 된다.

이러한 내용의 구현이 아래 파일에 적혀있다.

https://gist.github.com/koosaga/44532e5dec947132ee55da0458255e05

Suffix array를 만들었지만, 여전히 suffix trie를 어떻게 대체할 수 있는지는 감이 잡히지 않는다. 이를 위해서 LCP라는 배열을 또 하나 만들어야 한다. LCP[i] = 문자열의 [sfx[i-1], N-1] / [sfx[i], N-1] 이 있을 때, 겹치는 가장 긴 공통 prefix의 길이를 저장하는 것이다. 위에서 정의한 Longest common prefix 문제랑 상당히 유사한데, 이상하게 suffix array 상에서 인접한 것만 구한다. 이는, suffix array 상에서 인접한 것만 구한다면 모든 문자열의 LCP를 구할 수 있기 때문이다. 위에 정의한 longest common prefix가 이렇게 풀린다.

정확히는, s에서 시작하는 suffix와 t에서 시작하는 suffix를 생각해보자, rev[x] = (sfx[i] == x를 만족하는 i) 라고 정의했을 때, 일반성을 잃지 않고 rev[s] < rev[t]라고 생각해 보면, s와 t의 LCP는 Min(lcp[rev[s] + 1], lcp[rev[s] + 2] .. lcp[rev[e]]) 이다. 이는 구간에 대한 최솟값 문제(Range mininum query, RMQ) 이기 때문에, O(NlgN) / O(1) 전처리에 해결할 수 있다.

LCP는 O(N)에 짧은 코드로 구현할 수 있다. 이 부분에 대한 구현은 위 링크의 48 - 58줄에 적혀 있다. 알고리즘의 정당성에 관련된 부분은 이 블로그를 참고하라.

Suffix Array에 대한 정보를 알고 있으니, 이제 1번 문제를 풀기에는 충분하다. S $ T1 $ T2 $ T3 ... 의 형태로 모든 스트링을 붙여서 ($든 뭐든 원래 문자열에 안 나오는 문자면 상관이 없다.) suffix array를 만들고 LCP를 구하자. S에 있는 임의의 원소 p와, Ti과의 LCP가 |Ti| 이상이면 성공이다. 이 때, Ti의 LCP를 최대화 하려면 suffix array 상에서 가장 가까운 S의 원소를 보는 게 좋으므로, 왼쪽으로 가까운 / 오른쪽으로 가까운 S의 원소를 고르고, LCP를 구해서 하나라도 |Ti| 이상의 LCP를 가지는지 체크하면 전처리 후 쿼리당 O(1)에 문제를 해결할 수 있다. (온라인 풀이도 있다.)

몇가지 추가적인 연습 문제로 글을 마무리하겠다. 난이도순.

* BOJ 1605. 반복 문자열 https://www.acmicpc.net/problem/1605

더보기

LCP 배열의 최댓값을 찍으면 된다.

* BOJ 9249. 최장 공통 부분 문자열

더보기

위 문제랑 큰 차이 없이 풀린다. 다만, suffix array 상에서 인접한 문자가 "다른" 문자열에서 유래했는지 체크해야 한다.

* Balkan OI 2015. Clarkson https://www.acmicpc.net/problem/11555

더보기

S 문자열의 각각의 suffix i에 대해서, [i, p]가 T의 substring인 가장 긴 p를 찾으면, Parametric search 등으로 풀 수 있는 문제이다. 그렇게 쉬운 문제는 아니지만, 설명은 생략한다..

가장 긴 p를 찾는 것은 맨 위에 적어놓은 1번 문제에서 큰 차이가 없다. 각각의 i에 대해서, suffix array 상에서 가장 가까운 + T에서 유래된 원소를 찾고, LCP 중 max를 취하면 된다.

https://github.com/koosaga/olympiad/blob/master/Balkan/balkan15\_clarkson.cpp

* Polish OI 2005. Templates https://www.acmicpc.net/problem/7966

더보기

i가 답이 되기 위한 조건은, LCP(0, x) >= i인 모든 x를 통해서 문자열을 덮을 수 있어야 한다는 뜻이다. LCP(0, x) >= i를 만족하는 x와, 0, N을 정렬하고, 인접한 수의 차이가 모두 i 이하이면, 가능하다는 뜻이다.

이 제, i를 감소시키면서 문제를 풀자. 초기 적절한 자료구조에 [0, N]을 넣고, i를 감소시키면서 LCP(0, x) >= i를 만족하는 x를 순차적으로 넣는다. 이제 적절한 자료구조에 적절한 쿼리를 날리자 (..) 인접한 수의 차이의 최댓값이 i 이하인지 검사하고, 맞다면 i는 가능하다고 체크해두자.

이제 핵심은 "적절한 자료구조의" 구현이다. insert / maximum gap을 계산해야 한다. std::set이나 segment tree를 통해서 구현할 수 있다. 본인은 segment tree를 사용했다.

https://github.com/koosaga/olympiad/blob/master/POI/poi05\_sza.cpp

* Baltic OI 2004. Repeats http://www.spoj.com/problems/REPEATS/

더보기

반복 문자열의 길이를 L이라 고정시켰을 때, O(|S| / L)에 길이 L 문자열의 최대 반복 횟수 K를 구한다면, 총 O(NlgN)에 문제를 해결할 수 있다. O(NlgN)에 suffix array + LCP 다 전처리 했으니 O(|S| / L)에 문제를 해결해 보자.

[0, L-1] / [L, 2L-1] / [2L, 3L-1] 이런 식으로 문자열을 그룹으로 나누자. 만약에 (K, L) repeat가 존재한다면 (가령 L = 6, abcdef라고 하자)

[... abc] / [defabc] / [defabc] / [defabc] / (...) / [def ...]

와 같은 형태를 그룹에서 띄고 있을 것이다.

고 로, 각각의 인접한 블록에 대해서, LCP가 L 이상인 블록은 한꺼번에 처리해주자. 만약에 그러한 연속한 블록이 K개 있다면 일단 답이 K인건 먹고 들어간 거다. K+1일 가능성이 있어서, 그걸 처리해줘야 하는데, 역으로 뒤집어준 문자열에 대한 suffix array를 만들어주자. 이렇게 되면 longest common prefix 말고 suffix 역시 구할 수 있고, 이제 (블록의 끝 쪽에서의 common suffix) + (블록의 앞 쪽에서의 common prefix) >= L이면 K+1이 답이 될 가능성이 있다는 것을 알 수 있다.

https://github.com/koosaga/olympiad/blob/master/Baltic/baltic04\_repeats.cpp