백준 - 공통 부분 문자열 (5582) : JAVA

문제 유형
dp

풀이 방법 도출
문제의 조건은 다음과 같습니다.

1. 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.
2. 첫째 줄과 둘째 줄에 문자열이 주어진다. 문자열은 대문자로 구성되어 있으며, 길이는 1 이상 4000 이하이다.
3. 첫째 줄에 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이를 출력한다.

이 문제는 Longest Common Substring의 대표 문제입니다.
LCS는 2차원 배열을 통해 공통으로 연속된 문자열의 최대 길이를 구하는 알고리즘입니다.

int[][] dp = new int[a.length()+1][b.length()+1];

int maxLength = 0;

for (int i=1; i<=a.length(); i++) {
    char curA = a.charAt(i-1);
    for (int j=1; j<=b.length(); j++) {
        char curB = b.charAt(j-1);

        if (curA == curB) {
            dp[i][j] = dp[i-1][j-1] + 1;
            maxLength = Math.max(maxLength, dp[i][j]);
        }
    }
}

위와 같은 점화식으로 해결할 수 있습니다.

dp[i][j] = dp[i-1][j-1] + 1;

위 한 줄이 핵심인데, 이유는 다음과 같습니다.

1. dp[i-1][j-1]은 a의 i-1번째 문자와 b의 j-1문자에서 끝나는 최대 공통 부분 문자열의 길이이다.
2. +1을 하는 이유는 현재 a의 i번째 문자와 b의 j번째 문자가 같기 때문이다.
3. 공통 부분 문자열은 연속되어야하기 때문에 a의 i-1, b의 j-1의 문자가 같으면 해당 공통 부분 문자열에 연결될 수 있다.

시간 복잡도
O(N x M)

코드

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


public class Main {

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

        int[][] dp = new int[a.length()+1][b.length()+1];

        int maxLength = 0;

        for (int i=1; i<=a.length(); i++) {
            char curA = a.charAt(i-1);
            for (int j=1; j<=b.length(); j++) {
                char curB = b.charAt(j-1);

                if (curA == curB) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    maxLength = Math.max(maxLength, dp[i][j]);
                }
            }
        }

        System.out.println(maxLength);

    }

}