[백준 5582] 공통 부분 문자열

문제 링크 : https://www.acmicpc.net/problem/5582

이 문제는 dp를 이용하여 풀 수 있습니다. 공통 부분 문자열의 특징을 잘 생각해보면 두 문자열 str1과 str2가 있다고 했을 때 str1의 i번까지의 부분 문자와 str2의 j번까지의 부분 문자를 비교하는 방식으로 작동합니다. 따라서 dp[i][j] = str1의 1부터 i까지의 글자와 str2의 1부터 j까지의 글자 사이의 공통 부분 문자열 길이로 설정해서 dp의 최댓값을 출력하는 방식으로 문제를 해결하면 됩니다.

dp 배열을 채우는 방식은 크게 두 단계입니다. 먼저 두 공통 부분 문자열 중 서로 같은 문자가 존재한다면 dp배열은 최소 1을 확보하므로 각 문자열을 반복문을 돌려 같은 문자인 경우 각각의 인덱스의 dp를 1로 채웁니다.(ex str1의 i번 문자와 str2의 j번 문자가 같을 경우 dp[i][j] = 1)

그 다음 가장 긴 공통 부분 문자열을 얻기 위해 이전 문자열과 비교합니다. 만약 이전 문자열도 서로 같고 지금 문자열도 서로 같다면 dp[i][j]는 이전 dp[i-1][j-1]에 1만큼 더한 것이 됩니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

class Main{
    static String str1,str2;
    static int[][] dp;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str1 = br.readLine();
        str2 = br.readLine();

        // dp[i][j] = str1의 1부터 i까지의 글자와 str2의 1부터 j까지의 글자 사이의 공통 부분 문자열 길이
        dp = new int[str1.length()][str2.length()];

        // 두 문자열 중 서로 같은 문자가 있을 경우 dp[i][j] = 1
        for(int i=0;i<str1.length();i++){
            for(int j=0;j<str2.length();j++){
                if(str1.charAt(i) == str2.charAt(j)) dp[i][j] = 1;
            }
        }

        // 두 문자열 중 이전 문자도 서로 같고 현재 문자도 같을 경우 dp[i][j] = dp[i-1][j-1]+1
        for(int i=1;i<str1.length();i++){
            for(int j=1;j<str2.length();j++){
                if(str1.charAt(i-1) == str2.charAt(j-1) && str1.charAt(i) == str2.charAt(j))
                    dp[i][j] = dp[i-1][j-1]+1;
            }
        }

        // dp[i][j] 중 최댓값 출력
        int res = 0;
        for(int i=0;i<str1.length();i++){
            for(int j=0;j<str2.length();j++){
                res = Math.max(res,dp[i][j]);
            }
        }

        System.out.println(res);
    }
}