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

1. 문제

5582번: 공통 부분 문자열

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

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

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

---

2. 풀이

[LCS문제]와 비슷하지만 조금 더 쉬운 문제다. LCS는 연속될 필요 없이 최장 부분 문자열만 구하면 됐지만, 이 문제는 "연속된" 문자열을 알아내야 하기 때문에 A와 B의 문자가 다르다면 그 경우는 볼 필요 없이 넘기면 된다.

dp[i][j]에서, A와 B의 문자가 같다면 직전 dp[i-1][j-1]에서 1을 더한 값을 저장한다. LCS문제의 예제로 설명하면 이런 식이다.

최장길이를 구해야 하기 때문에 answer 변수에 max값을 저장해둔다.

import java.io.*;

public class BOJ_5582_공통부분문자열 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      char[] A = in.readLine().toCharArray();
      char[] B = in.readLine().toCharArray();
      int[][] dp = new int[A.length+1][B.length+1];

      int answer = 0;
      for(int i=1;i<=A.length;i++){
         for(int j=1;j<=B.length;j++){
            if(A[i-1] != B[j-1]) continue;
            dp[i][j] = dp[i-1][j-1]+1;
            answer = Math.max(answer, dp[i][j]);
         }
      }

      System.out.println(answer);
   }
}

---

3. 결과