[백준/JAVA] BOJ 5582 - 공통 부분 문자열

이게 뭐라고 끙끙댄 걸까

👀 문제

5582번: 공통 부분 문자열 ✨ 골드 5

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

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

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

예제 입력

ABRACADABRA
ECADADABRBCRDARA

예제 출력

5

🔑 키포인트

다이나믹 프로그래밍

✍️ 코드

📍 dp[i][j] = 첫 번째 문자열의 j번째까지와 두 번째 문자열의 i번째까지의 공통 부분 길이
💡 점화식 dp[i][j] = dp[i -1][j - 1] + 1 (문자가 같은 경우)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ5582_공통부분문자열 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine();
        String s2 = br.readLine();
        int[][] dp = new int[s2.length() + 1][s1.length() + 1];
        int answer = 0;

        for (int i = 1; i < s2.length() + 1; i++) {
            for (int j = 1; j < s1.length() + 1; j++) {
                if (s2.charAt(i - 1) == s1.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    answer = Math.max(answer, dp[i][j]);
                }
            }
        }
        System.out.println(answer);
    }
}