[BOJ] 백준 5582 공통 부분 문자열 (Java)

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

 Input 

ABRACADABRA

ECADADABRBCRDARA

　 

 Output 

5

공통 부분 연속 문자열을 구하기 위해서 DP 이용.

[점화식]

다음 두 문자열이 주어졌다고 가정하여, 도표를 통해 분석해보자.

ABRAC

BABRDC

 

→ A[i] == B[j]이면 LCS[i-1][j-1] + 1

→ A[i] != B[j]이면 『0』

결과적으로 다음과 같다.

---

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        char[] A = sc.next().toCharArray();
        char[] B = sc.next().toCharArray();
        int[][] LCS = new int[A.length+1][B.length+1];
         
        int answer = Integer.MIN_VALUE;
        for(int i=1; i<=A.length; i++) {
            for(int j=1; j<=B.length; j++) {
                if(A[i-1] == B[j-1]) {
                    LCS[i][j] = LCS[i-1][j-1] + 1; 
                }
                answer = Math.max(answer, LCS[i][j]);
            }
        }
         
        System.out.println(answer);
    }
}