백준 공통부분문자열 5582 java

문제링크

문제 접근

• 코테에 자주 나오는 문자열을 연습하자..........
• 두 문자열에서 공통 부분 문자열의 최대 길이

코드

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

public class baek_5582 { // 가장 긴 공통 문자열 길이
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String A = br.readLine();
        String B = br.readLine();
        int N = A.length();
        int M = B.length();
        int[][] LCS = new int[N+1][M+1];
        int answer = 0;

        for(int i=1;i<=N;i++){
            char A_now = A.charAt(i-1);
            for(int j=1;j<=M;j++){
                char B_now = B.charAt(j-1);
                if(A_now == B_now) {
                    LCS[i][j] = LCS[i-1][j-1] + 1;
                    answer = Math.max(answer,LCS[i][j]);
                }
            }
        }
        System.out.print(answer);
    }
}

결과

정리

• 각 문자열 길이로 2차원 배열을 만들어서 DP