1605번: 반복 부분문자열

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

 

언어 : Kotlin

 

문제 설명 :

알파벳 소문자로 이루어진 길이 L인 문자열이 있다. 이 문자열의 부분문자열 중, 적어도 한 번은 반복되는 (다시 말해서, 전체 문자열에서 두 번 이상 나타나는) 부분문자열을 '반복 부분문자열'이라고 부르자.

문자열이 주어지면, 가장 긴 '반복 부분문자열'의 길이를 구하는 프로그램을 작성하시오.

 

입력 :

첫째 줄에 문자열의 길이 L(1 ≤ L ≤ 200,000)이 주어진다. 둘째 줄에는 문자열을 이루는 L개의 알파벳 소문자들이 띄어쓰기 없이 주어진다.

 

출력 :

첫째 줄에 가장 긴 '반복 부분문자열'의 길이를 출력한다. 만일 '반복 부분문자열'이 하나도 존재하지 않는다면 0을 출력한다.

 

제한 사항 :

• 시간 제한 : 2초
• 메모리 제한 : 128MB

 

입출력 예 :

입력	출력
28 tellmetellmetetetetetetellme	11
5 jykim	0

 

풀이 : 

Suffix Array를 만들고 LCP 배열을 구해 거기서 제일 큰 값을 리턴하면 되는 문제.

멘버 마이어스 알고리즘을 사용했으며 이전에 풀었던 기억이 있어 그대로 가져다 썼다.

main 부분만 코드가 바뀌고 Suffix Array를 만들고 LCP 배열을 구하고 하는 부분은 완전 똑같다.

 

https://small-stepping.tistory.com/857

9248번: Suffix Array

 

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 l = readLine().toInt()
    val str = readLine()
    val suffixArray = getSuffixArray(str)
    val result = getLCPArray(str, suffixArray).maxOfOrNull { it }
    bw.write(if (result == null) "0" else "$result")
    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]
    }
}