9253번: 스페셜 저지

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

 

언어 : Kotlin

 

문제 설명 :

9249번 문제 (최장 공통 부분 문자열)의 채점 프로그램을 작성하시오.

문제의 조건은 동일하다. 편의상 사용자가 출력한 문자열의 길이가 문제의 답과 동일하고, 답은 0보다 크다고 가정한다.

 

입력 :

두 문자열 A와 B가 한 줄에 하나씩 주어진다. 두 문자열 길이의 합은 20만을 넘지 않는다.

세 번째 줄에 사용자가 출력한 문자열이 주어진다. 입력으로 주어지는 모든 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 20만을 넘지 않는다.

 

출력 :

답이 맞으면 YES, 틀리면 NO를 출력한다.

 

제한 사항 :

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

 

입출력 예 :

입력	출력
yeshowmuchiloveyoumydearmotherreallyicannotbelieveit yeaphowmuchiloveyoumydearmother howmuchiloveyoumydearmother	YES

 

풀이 : 

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

lateinit var rank: IntArray

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

    val a = readLine()
    val b = readLine()
    val input = readLine()

    val ab = "$a#$b"
    val suffixArr = getSuffixArray(ab, ab.length)
    val lcpArr = getLCPArray(ab, suffixArr, ab.length)

    var maxL = 0
    var maxIdx = 0
    for (i in 1 until ab.length) {
        if ((suffixArr[i - 1]!! < a.length && suffixArr[i]!! > a.length) || (suffixArr[i - 1]!! > a.length && suffixArr[i]!! < a.length)) {
            if (lcpArr[i] > maxL) {
                maxL = lcpArr[i]
                maxIdx = suffixArr[i]!!
            }
        }
    }

    val result = ab.substring(maxIdx, maxIdx + maxL)

    bw.write(if (result == input) "YES" else "NO")
    bw.flush()
    bw.close()
}

fun getSuffixArray(input: String, abLength: Int): Array<Int?> {
    val suffixArray = arrayOfNulls<Int>(abLength)
    rank = IntArray(abLength)
    for (i in 0 until abLength) {
        suffixArray[i] = i
        rank[i] = input[i] - 'a'
    }

    var length = 1
    while (length < abLength) {
        val l = length
        Arrays.sort<Int?>(suffixArray) { i: Int?, j: Int? ->
            if (rank[i!!] != rank[j!!]) {
                return@sort rank[i].compareTo(rank[j])
            }
            val rankI = if ((i + l < abLength)) rank[i + l] else -1
            val rankJ = if ((j + l < abLength)) rank[j + l] else -1
            rankI.compareTo(rankJ)
        }

        val tempRank = IntArray(abLength)
        tempRank[suffixArray[0]!!] = 0
        for (i in 1 until abLength) {
            tempRank[suffixArray[i]!!] = tempRank[suffixArray[i - 1]!!]
            if (rank[suffixArray[i]!!] != rank[suffixArray[i - 1]!!] ||
                (if (suffixArray[i]!! + l < abLength) rank[suffixArray[i]!! + l] else -1) !=
                (if (suffixArray[i - 1]!! + l < abLength) rank[suffixArray[i - 1]!! + l] else -1)
            ) {
                tempRank[suffixArray[i]!!]++
            }
        }
        rank = tempRank
        length *= 2
    }

    return suffixArray
}

fun getLCPArray(input: String, sa: Array<Int?>, sbLength: Int): IntArray {
    val lcp = IntArray(sbLength)
    var h = 0
    for (i in 0 until sbLength) {
        if (rank[i] > 0) {
            val j: Int = sa[rank[i] - 1]!!
            while (i + h < sbLength && j + h < sbLength && input[i + h] == input[j + h]) {
                h++
            }
            lcp[rank[i]] = h
            if (h > 0) h--
        }
    }

    return lcp
}