5582번: 공통 부분 문자열

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

5582번: 공통 부분 문자열

언어 : Kotlin

 

문제 설명 :

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.

어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다.

두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다. 또, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 가장 긴 공통 부분 문자열은 빈 문자열이다.

 

입력 :

첫째 줄과 둘째 줄에 문자열이 주어진다. 문자열은 대문자로 구성되어 있으며, 길이는 1 이상 4000 이하이다.

 

출력 :

첫째 줄에 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이를 출력한다.

 

제한 사항 :

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

입출력 예 :

입력	출력
ABRACADABRA ECADADABRBCRDARA	5
UPWJCIRUCAXIIRGL SBQNYBSBZDFNEV	0

 

풀이 : 

메모이제이션(https://wondytyahng.tistory.com/entry/memoization-%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98)를 활용한 문제

메모이제이션(Memoization) 개념 및 예시, 재귀(recursion)

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

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

    val s1 = readLine()
    val s2 = readLine()
    var result = 0
    val arr = Array(s1.length + 1) { IntArray(s2.length + 1) }

    for (i in 1 .. s1.length) {
        for (j in 1 .. s2.length) {
            if (s1[i - 1] == s2[j - 1]) {
                arr[i][j] = arr[i - 1][j - 1] + 1
                result = Math.max(result, arr[i][j])
            }
        }
    }

    bw.write("$result")
    bw.flush()
    bw.close()
}