백준 5582번 - 공통 부분 문자열

문제

백준 5582번 - 공통 부분 문자열

아이디어

• 기본적인 LCS 문제 해결 과정으로 해결한다.

예상 시간 복잡도

• 두 문자열의 길이 : N, M
• 예상 시간 복잡도 : O(N x M)

코드 구현

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

public class BJ_5582 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        char[] a = br.readLine().toCharArray();
        char[] b = br.readLine().toCharArray();

        int lenA = a.length;
        int lenB = b.length;

        int[][] dp = new int[lenA + 1][lenB + 1];

        int max = 0;

        for (int i = 1; i <= lenA; i++) {
            for (int j = 1; j <= lenB; j++) {
                if (a[i - 1] == b[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                max = Math.max(max, dp[i][j]);
            }
        }

        System.out.println(max);
    }
}