9248번: Suffix Array

문제 출처 : https://www.acmicpc.net/problem/9248

9248번: Suffix Array

언어 : Kotlin

 

문제 설명 :

Suffix Array란, 문자열 S가 있을 때 그 접미사들을 정렬해 놓은 배열이다. 예를 들어, 문자열 S=banana의 접미사는 아래와 같이 총 6개가 있다.

Suffix	i
banana	1
anana	2
nana	3
ana	4
na	5
a	6

 

이를 Suffix 순으로 정렬하면 아래와 같다.

 

Suffix	i
a	6
ana	4
anana	2
banana	1
na	5
nana	3

 

정렬된 i의 배열 [6,4,2,1,5,3]을 S의 Suffix Array라고 한다.

문자열 S의 LCP Array는 Suffix Array를 구한 다음, 각 Suffix마다 정렬된 상태에서 바로 이전 Suffix와의 LCP (Longest Common Prefix, 최장 공통 접두사)의 길이를 배열에 담은 것이다. 위의 예에서 LCP Array는 [x,1,3,0,0,2]가 된다.

길이가 50만보다 작거나 같은 문자열이 주어졌을 때, Suffix Array와 LCP Array를 구하는 프로그램을 작성하시오.

 

입력 :

첫째 줄에 알파벳 소문자로만 이루어진 문자열 S가 주어진다. S의 길이는 50만보다 작거나 같다.

 

출력 :

첫째 줄에는 Suffix Array를, 둘째 줄에는 LCP Array를 공백으로 구분하여 출력한다. LCP Array의 첫 값은 항상 'x'이다.

 

제한 사항 :

• 시간 제한 : 3초
• 메모리 제한 : 256MB

 

입출력 예 :

입력	출력
abracadabra	11 8 1 4 6 9 2 5 7 10 3 x 1 4 1 1 0 3 0 0 0 2

 

풀이 : 

처음에 메모리 문제로 틀렸다.

이유로는 SuffixArray를 구할 때, 브루트포스를 통해 리스트에 하나하나 추가했었고, 그게 문제였다고 생각한다.

LCS Array를 구하는 방법은 검색을 통해 구현방법을 알아내어 테스트 결과 IDE 상에선 문제 없이 돌아갔기 때문이다.

 

좀 더 검색해보니 이전에 문제 풀때도 그랬지만 기본 내장되어 있는 라이브러리 함수들은 성능이 평범하기 때문에 코딩테스트처럼 특수하게 제한사항이 존재하는 환경에선 기준 통과에 어려움이 존재하는 듯 하다.

 

그래서 SuffixArray를 만들때 반복문 + 정렬알고리즘을 사용하는 것이 아니라, 멘버 마이어스 알고리즘을 사용한다고 한다. 멘버 마이너스 알고리즘은 접미사 배열에서 처음 제안한 논문에서 제시된 것으로, 정렬하는 문자열들이 한 문자열의 접미사라는 점을 이용해 수행시간을 낮춘다는 것이다. 해당 알고리즘은 접미사들의 목록을 여러번 정렬하는데, 매번 그 기준을 바꾼다는 것.

1. 처음에는 접미사의 첫 글자만을 기준으로 정렬한다.
2. 이후에는 접미사의 첫 네 글자 기준으로 정렬한다.
3. 이렇게 logN번 정렬하면 원하는 접미사 배열을 얻게된다.

여러번 정렬함에도 성능이 더 좋은 이유는 이전 정렬에서 얻은 정보를 통해 두 문자열의 대소 비교를 O(1)에 할 수 있기 때문이다.

 

멘버 마이너스 알고리즘에 해당하는 것이 SuffixArray를 구하는 과정에 포함되는 2가지 코드다.

아래 전체 코드에 작성된, getSuffixArray() 함수와 CompareUsing2T 클래스

 

이후 LCS 배열을 구하게 되는데 이것은 카사이 알고리즘을 사용했다. 카사이 알고리즘은 접미사 배열이 사전순으로 정렬되어 있다는 특성을 이용한 것으로, 해당 알고리즘은 가장 긴 접미사(원본 문자열)부터 길이가 짧아지는 순서대로 접미사를 탐색하며 최장공통접두사의 길이를 구하는 방식이다.

이 과정이 아래 코드의 getLCSArray()이다.

 

멘버 마이너스 알고리즘을 통한 접미사 배열과 카사이 알고리즘을 통한 LCS 배열 구하는 방법에 대한 더 자세한 내용은 다음 블로그의 글을 참고하면 좋다.

https://loosie.tistory.com/798#%EC%A0%91%EB%AF%B8%EC%82%AC_%EB%B0%B0%EC%97%B4_%EB%A7%8C%EB%93%A4%EA%B8%B0_-_%EB%A9%98%EB%B2%84_%EB%A7%88%EC%9D%B4%EC%96%B4%EC%8A%A4_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[알고리즘] 접미사 배열(Suffix Array)와 LCP 배열(Lognest Common Prefix Array) (Java)

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*


fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val input = readLine()
    val suffixArray = getSuffixArray(input)
    val lcsArray = getLCPArray(input, suffixArray)

    for (i in suffixArray.indices) {
        suffixArray[i] += 1
    }

    bw.appendLine(suffixArray.joinToString(" "))
    bw.write("x ${lcsArray.joinToString(" ")}")
    bw.flush()
    bw.close()
}

fun getSuffixArray(input: String): ArrayList<Int> {
    val n = input.length
    var t = 1
    val perm = ArrayList<Int>()
    var group = IntArray(n + 1)

    for (i in 0 until n) {
        perm += i
        group[i] = input[i] - 'a'
    }

    group[n] = -1

    val compareUsing2T = CompareUsing2T(n, t, group)
    while (t < n) {
        Collections.sort(perm, compareUsing2T.comparator())
        t *= 2
        if (t >= n) break

        val newGroup = IntArray(n + 1).also {
            it[perm[0]] = 0
            it[n] = -1
        }

        for (i in 1 until n) {
            if (compareUsing2T.comparator().compare(perm[i - 1], perm[i]) < 0) newGroup[perm[i]] = newGroup[perm[i - 1]] + 1
            else newGroup[perm[i]] = newGroup[perm[i - 1]]
        }

        group = newGroup
        compareUsing2T.changeValues(t, group)
    }

    return perm
}

fun getLCPArray(input: String, sa: ArrayList<Int>): IntArray {
    val n = sa.size
    val lcp = IntArray(n - 1)
    val isa = IntArray(n)

    for (i in 0 until n) {
        isa[sa[i]] = i
    }

    var k = 0
    for (i in 0 until n) {
        val idx = isa[i]
        if (idx == n - 1) continue

        val j = sa[idx + 1]
        while (i + k < n && j + k < n) {
            if (input[i + k] != input[j + k]) break
            k++
        }

        lcp[idx] = k
        if (k > 0) k--
    }

    return lcp
}

class CompareUsing2T(private val n: Int, private var t: Int, private var group: IntArray) {
    fun changeValues(t: Int, group: IntArray) {
        this.t = t
        this.group = group.copyOf(group.size)
    }

    fun comparator() = Comparator<Int> { o1, o2 ->
        if (group[o1] != group[o2]) return@Comparator group[o1] - group[o2]

        var left = o1 + t
        var right = o2 + t

        if (o1 + t > n) left = n
        if (o2 + t > n) right = n

        group[left] - group[right]
    }
}