9249번: 최장 공통 부분 문자열

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

 

언어 : Kotlin

 

문제 설명 :

문자열 (T=t1t2 ... tm)가 문자열 (S=s1s2 ... sn)의 부분 문자열이 되려면, (s{i+1}s{i+2} ... s{i+m} = T)를 만족하는 (0 ≤ i ≤ n-m)가 있어야 한다.

두 문자열 (A)와 (B)가 주어졌을 때, 두 문자열의 공통 부분 문자열의 최대 길이와 그 부분 문자열을 구하는 프로그램을 작성하시오.

 

입력 :

두 문자열 (A)와 (B)가 한 줄에 하나씩 주어진다. 두 문자열 길이의 합은 20만을 넘지 않는다. 주어지는 문자열은 알파벳 소문자로만 이루어져 있다.

 

출력 :

첫째 줄에 두 문자열의 최장 공통 부분 문자열의 길이를 출력한다.
둘째 줄에 해당 부분 문자열을 출력한다.
답이 여러 가지인 경우에는 아무거나 출력한다.

 

제한 사항 :

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

 

입출력 예 :

입력	출력
yeshowmuchiloveyoumydearmotherreallyicannotbelieveit yeaphowmuchiloveyoumydearmother	27 howmuchiloveyoumydearmother

 

풀이 : 

커뮤니티에 있는 힌트인 a 문자열과 b 문자열을 결합한다.

"$a#$b"로 결합했고, 이를 기준으로 suffixArr와 lcpArr를 구한다.

 

 

두 접미사의 사전 순서를 비교해 Rank를 갱신하고 각 접미사의 시작 인덱스를 포함하는 배열을 사전순으로 정렬한다.

정렬된 접미사 배열에서 인접한 접미사들의 가장 긴 공통 접두사를 계산한다.

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

lateinit var rank: IntArray

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

    val a = readLine()
    val b = 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]!!
            }
        }
    }

    bw.appendLine("$maxL").append(ab.substring(maxIdx, maxIdx + maxL))
    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
}