BaekJoon(5582)::공통 부분 문자열

문제

5582번: 공통 부분 문자열

문제파악

해당문제는 LCS와 비슷하게 풀 수 있는 문제이다.

다만, 기존 LCS는 Longest-Common-Subsequence라면 해당 문제는 Longest-Common-SubString 문제이다.

 

위 두 LCS또한 결국 DP문제이기 때문에 점화식을 통해 문제를 해결하면 쉽게 해결가능하다.

문제풀이

해당문제의 LCS(Longest Common SubString)의 점화식을 구해보면 다음과 같다.

$$ LCS(X_i, Y_j) = \begin{cases} 0 & \mbox{if } i=0 \mbox{ or } j=0 \mbox{ or } X_i \ne Y_j  \\ LCS(X_{i-1}, Y_{j-1}) & \mbox{if } X_i = Y_j \end{cases}$$ 

해당 점화식을 통해 DP를 이용하여 작성하면 문제가 해결된다.

import java.util.Scanner;

public class Main {
    static int max(int a, int b){
        return a>b?a:b;
    }

    static int lcs(char[] X, char[] Y, int m, int n){
        int DP[][] = new int[m+1][n+1];
        int lcs_length = 0;

        for(int i = 0;i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0 || X[i - 1] != Y[j - 1]){
                    DP[i][j] = 0;
                }
                else {
                    DP[i][j] =  1 + DP[i-1][j-1];
                }

                lcs_length = max(lcs_length, DP[i][j]);
            }
        }

        return lcs_length;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        String str1 = in.nextLine();
        String str2 = in.nextLine();

        char[] X=str1.toCharArray();
        char[] Y=str2.toCharArray();

        int lcs_length = lcs(X, Y, str1.length(), str2.length());

        System.out.println(lcs_length);
    }
}