LCS(Longest Common Subsequense, 최장 공통 부분 수열)

LCS란 주어진 모든 수열들의 부분 수열(연속적이지 않아도 된다)이 되는 수열 중 가장 긴 것이다.

 

 

str1과 str2라는 두 수열이 주어졌다고 하자.

 

P] str1과 str2의 부분수열 중 가장 긴 수열의 길이를 구하라.

 

Sol)

str1의 시작부터 x번째까지의 문자열과 str2의 시작부터 y번째까지의 문자열의 LCS를 f(x, y)라고 하자.

 

이때 f(m, n)은,

 1) str1의 m번째 문자 == str2의 n번째 문자일때

    f(m, n) = f(m - 1, n - 1) + 1

     : 현재 일치하는 문자를 제외하고 나머지 문자열들의 LCS가 현재 문자열들의 LCS보다 하나 짧아야 하므로 자명하다.

   

 2) str1의 m번째 문자 != str2의 n번째 문자일때

    f(m, n) = max(f(m - 1, n) , f(m, n - 1))

    : 현재 위치의 문자들이 일치하지 않으므로, str1에서 현재 문자를 제외한 버전인 f(m - 1, n)과 str2에서 현재 문자를 제외한 버전인 f(m, n - 1)중 큰것을 고르면 된다.

 

 

Kotlin Code

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.max

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var str = Array<String>(2){""}
    str[0] = readLine()
    str[1] = readLine()
    var arr = Array(str[0].length + 1){IntArray(str[1].length + 1){0} }

    for(i in 0..str[0].length - 1){
        for(j in 0..str[1].length - 1){
            if(str[0][i] == str[1][j]){
                arr[i + 1][j + 1] = arr[i][j] + 1
            }else{
                arr[i + 1][j + 1] = max(arr[i][j + 1], arr[i + 1][j])
            }
        }
    }
    print("${arr[str[0].length][str[1].length]}\n")
}