BOJ 5582 공통 부분 문자열

https://www.acmicpc.net/problem/5582

문제

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

어떤 문자열 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

예제 입력 2

UPWJCIRUCAXIIRGL
SBQNYBSBZDFNEV

예제 출력 2

0

---

코드

이전에 BOJ 9251 LCS 이라는 문제를 푼 적이 있는데, 이와 매우 유사한 문제였다.

다만, LCS는 가장 긴 공통 부분 수열이기 때문에 문자열이 붙어있지 않아도 상관 없었지만 이번 문제는 문자열이 붙어있어야 한다는 부분이 다르다.

이번 문제의 코드를 LCS 문제의 코드와 비교해보면 조건문 else 부분을 제외한 나머지 알고리즘은 동일한 것을 볼 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static String input1;
    static String input2;
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        input1 = br.readLine();
        input2 = br.readLine();
        dp = new int[input1.length() + 1][input2.length() + 1];

        int answer = calculateMaxLength();
        System.out.println(answer);
    }

    static int calculateMaxLength() {
        int maxLength = 0;

        for (int i = 0; i < input1.length(); i++) {
            for (int j = 0; j < input2.length(); j++) {
                if(input1.charAt(i) == input2.charAt(j)) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                    maxLength = Integer.max(maxLength, dp[i + 1][j + 1]);
                }
            }
        }

        return maxLength;
    }
}