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

문제

1753번: 최단경로

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

어떤 문자열 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 이하이다.

 

출력

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

 

입출력 예제

 

풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] arr1 = br.readLine().split("");
        String[] arr2 = br.readLine().split("");

        int[][] ans = new int[arr1.length + 1][arr2.length + 1];
        int max = 0;

        for (int i = 1; i <= arr1.length; i++) {
            for (int j = 1; j <= arr2.length; j++) {
                // 문자가 같다면 이전 길이까지 계산한 최대값에 1을 더해준다.
                if (arr1[i - 1].equals(arr2[j - 1])) {
                    ans[i][j] = ans[i - 1][j - 1] + 1;
                    max = Math.max(max, ans[i][j]);
                }
            }
        }

        System.out.println(max);
    }
}

주어진 입출력 예제로 계산했을 때 ans 배열은 아래와 같이 완성된다. 

 

+ 추가

if (arr1[i - 1].equals(arr2[j - 1])) {
    ans[i][j] = ans[i - 1][j - 1] + 1;
    max = Math.max(max, ans[i][j]);
} else {
    ans[i][j] = Math.max(ans[i - 1][j], ans[i][j - 1]);
}

일반적으로 최장 공통 부분 수열을 찾을 때는 같지 않을 때 바로 위나 왼쪽 값 중 큰 값을 채택하여 사용한다. 그러나 해당 문제에서 찾을 것은 최장 공통 문자열이기 때문에 else 구문을 두지 않았다. 이유는 공통 부분 수열은 문자 사이를 건너뛰면서 공통되는 가장 긴 문자열을 찾는 것이기 때문에 값이 누적되고, 공통 문자열은 연속되는 가장 긴 문자열을 찾는 것이기 때문에 누적 값을 사용하지 않는 것이다. 만약 해당 문제가 최장 공통 부분 수열을 찾는 문제라면, 정답은 8이 된다.