[백준] 5582번 - 공통 부분 문자열 [Java][C++]

문제 링크

---

1. 문제 풀이

두 문자열의 가장 긴 공통 부분 문자열을 찾는 문제로 최장 공통 부분 문자열 알고리즘(LCS)을 활용하면 해결할 수 있다. 최장 공통 부분 수열(Longest Common Subsequence)이 아니라 최장 공통 부분 문자열(Longest Common Substring)임에 주의해야 한다.

최댓값의 경우도 최장 공통 부분 수열은 dp 테이블의 마지막 인덱스에서 얻을 수 있지만, 최장 공통 부분 문자열은 어디에 저장됐을지 알 수 없다. 따라서 dp 테이블에서 가장 큰 값을 매번 갱신하는 방식으로 구현했다.

---

2. 코드

1. Bottom-Up dp [Java]

dp 테이블 앞에 패딩을 한 칸씩 줬다.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        char[] str1 = br.readLine().toCharArray();
        char[] str2 = br.readLine().toCharArray();
        int N = str1.length;
        int M = str2.length;

        int[][] dp = new int[1 + N][1 + M];
        int max = 0;

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    max = Math.max(max, dp[i][j]);
                }
            }
        }

        System.out.println(max);
    }
}

2. Bottom-Up dp [C++]

dp 테이블 앞에 패딩을 한 칸씩 줬다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s1, s2;
    cin >> s1 >> s2;

    int n = s1.size();
    int m = s2.size();

    vector<vector<int>> dp(1 + n, vector<int>(1 + m));
    int mx = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                mx = max(mx, dp[i][j]);
            }
        }
    }

    cout << mx;
}

---

3. 풀이 정보

1. Bottom-Up dp [Java]

언어	시간	메모리	코드 길이
Java 11	212 ms	76868 KB	733 B

2. Bottom-Up dp [C++]

언어	시간	메모리	코드 길이
C++ 17	68 ms	64808 KB	530 B

---