[ BOJ ][JAVA][5582] 공통 부분 문자열

www.acmicpc.net/problem/5582

5582번: 공통 부분 문자열

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	7874	3235	2482	43.407%

문제

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

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

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

입력

첫째 줄과 둘째 줄에 문자열이 주어진다. 문자열은 대문자로 구성되어 있으며, 길이는 1 이상 4000 이하이다.

출력

첫째 줄에 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이를 출력한다.

예제 입력 1

ABRACADABRA
ECADADABRBCRDARA

예제 출력 1

5

코드

/*
    공통 부분 문자열
    DP
    LCS를 이용한 DP를 수행하면 된다.
*/
import java.io.*;
import java.util.*;
public class p5582 {
    static char[] str1, str2;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str1 = br.readLine().toCharArray();
        str2 = br.readLine().toCharArray();

        int len1 = str1.length;
        int len2 = str2.length;

        int[][] dp = new int[len1 + 1][len2 + 1];
        int max = 0;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                // 두 문자가 서로 같다면 이전에 거에서 길이를 하나 추가하고
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    // 최대 길이를 갱신한다.
                    max = Math.max(max, dp[i][j]);
                }
                // 같지 않다면 다시 길이는 1부터 초기화 되어야 한다.
            }
        }
        System.out.println(max);
    }
}